Awesome q2a theme
Ask us anything
Toggle navigation
Email or Username
Password
Remember
Login
Register
|
I forgot my password
Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Blogs
Previous Year
Exams
Recent questions tagged context-free-languages
+1
vote
2
answers
#toc #self_doubts #cfl
$L={\;\{\;a^{(m+n)}b^{(m+k)}c^{(k+n)}}, m,n,k ≥ 0 \;\}$ $L$ is CFL or DCFL? My logic is push all $a’s$ and then pop $m$ $b’s$ and push $k$ $b’s$, so here we need non determinism, so it should be CFL and not DCFL. Can anyone design a DPDA for it?
asked
Sep 2, 2020
in
Theory of Computation
by
suvradip das
(
119
points)
|
344
views
theory-of-computation
selfdoubt
pushdown-automata
context-free-languages
0
votes
1
answer
Chomsky Classification
which grammars of Chomsky Classification allows (S → ε) in its production rules ?
asked
Aug 19, 2020
in
Theory of Computation
by
Akshay sinha
(
9
points)
|
42
views
theory-of-computation
context-free-languages
context-sensitive-languages
+1
vote
2
answers
Self Doubt Peter Linz 5th edition: Exercise 8.1, Q13 [CFL Pumping Lemma]
asked
Aug 16, 2020
in
Theory of Computation
by
pritishc
(
23
points)
|
47
views
pumping-lemma
context-free-languages
0
votes
0
answers
TOC(self doubt-classification into the language)
Came to read and also got to know as a shortcut about classification of a Language on the basis of the comparisons into CFL or CSL.Is it really the standard method or is it the short trick or just an ill-defined way of attempting a question. This post can be taken as a reference – https://gateoverflow.in/26952/%23toc
asked
Jul 13, 2020
in
Theory of Computation
by
prajjwalsingh_11
(
15
points)
|
14
views
theory-of-computation
pumping-lemma
context-free-languages
context-sensitive-languages
0
votes
1
answer
Context Free Language
Is this CFL? L = {wcwr | w, c ϵ {0,1}+ and |c| = 2}
asked
Jul 1, 2020
in
Theory of Computation
by
sameer2009
(
5
points)
|
17
views
theory-of-computation
context-free-languages
+1
vote
1
answer
pushdown automata #CFL
Is the following language context-free language(CFL) or not? If yes, then is it Deterministic-CFL (DCFL)? L={ $a^i b^j$ where $i\neq 2*j+1$ and $j \geq 1$ and $i\geq 1$ }
asked
Jun 28, 2020
in
Theory of Computation
by
rgoyal
(
11
points)
|
50
views
theory-of-computation
pushdown-automata
context-free-languages
0
votes
0
answers
Peter Linz Exercise-8.2 Context Free Lnaguages
Show that the following language is context free L={$w\epsilon (a, b)$* : $n_{a}(w)=n_{b}(w)$, w does not contain the substring aab}
asked
Jun 16, 2020
in
Theory of Computation
by
aditi19
(
43
points)
|
20
views
theory-of-computation
peter-linz
context-free-languages
0
votes
0
answers
Peter Linz Theory of Computation Exercise 5.1 Question-15
asked
Jun 11, 2020
in
Theory of Computation
by
aditi19
(
43
points)
|
24
views
theory-of-computation
peter-linz
context-free-languages
0
votes
0
answers
GATE2018-35 Video Solution
Consider the following languages: $\{a^mb^nc^pd^q \mid m+p=n+q, \text{ where } m, n, p, q \geq 0 \}$ $\{a^mb^nc^pd^q \mid m=n \text{ and }p=q, \text{ where } m, n, p, q \geq 0 \}$ ... Which of the above languages are context-free? I and IV only I and II only II and III only II and IV only
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)
|
8
views
gate2018
theory-of-computation
identify-class-language
context-free-languages
normal
video-solution
0
votes
0
answers
GATE2016-1-42 Video Solution
Consider the following context-free grammars; $G_1 : S \to aS \mid B, B \to b \mid bB$ $G_2 : S \to aA \mid bB, A \to aA \mid B \mid \varepsilon,B \to bB \mid \varepsilon$ Which one of the following pairs of languages is generated by $G_1$ and $G_2$ ... $\{ a^mb^n \mid m > 0 \text{ or } n>0\}$
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)
|
11
views
gate2016-1
theory-of-computation
context-free-languages
normal
video-solution
0
votes
0
answers
GATE2017-1-10 Video Solution
Consider the following context-free grammar over the alphabet $\Sigma = \{a,b,c\}$ with $S$ as the start symbol:$S \rightarrow abScT \mid abcT$$T \rightarrow bT \mid b$ ... $\{\left ( ab \right )^{n}\left ( cb^{n} \right )^{m} \mid m,n \geq 1 \}$
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)
|
4
views
gate2017-1
theory-of-computation
context-free-languages
normal
video-solution
0
votes
0
answers
GATE2015-3-32 Video Solution
Which of the following languages are context-free? $L_1: \left\{a^mb^na^nb^m \mid m, n \geq 1\right\}$ $L_2: \left\{a^mb^na^mb^n \mid m, n \geq 1\right\}$ $L_3: \left\{a^mb^n \mid m = 2n +1 \right\}$ $L_1$ and $L_2$ only $L_1$ and $L_3$ only $L_2$ and $L_3$ only $L_3$ only
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)
|
7
views
gate2015-3
theory-of-computation
context-free-languages
normal
video-solution
0
votes
0
answers
GATE2003-51 Video Solution
Let $G=\left(\left\{S\right\}, \left\{a,b\right\},R,S\right)$ be a context free grammar where the rule set R is $S \to a S b \mid S S \mid \epsilon$ Which of the following statements is true? $G$ is not ambiguous There ... $L(G)$ We can find a deterministic finite state automaton that accepts $L(G)$
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)
|
3
views
gate2003
theory-of-computation
context-free-languages
normal
video-solution
0
votes
0
answers
GATE2009-12, ISRO2016-37 Video Solution
$S \to aSa \mid bSb\mid a\mid b$ The language generated by the above grammar over the alphabet $\{a,b\}$ is the set of: all palindromes all odd length palindromes strings that begin and end with the same symbol all even length palindromes
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)
|
5
views
gate2009
theory-of-computation
context-free-languages
easy
isro2016
video-solution
0
votes
0
answers
GATE2016-1-16 Video Solution
Which of the following languages is generated by the given grammar? $S \rightarrow aS \mid bS \mid \varepsilon$ $\{ a^nb^m \mid n,m \geq 0\}$ $\{ w \in \{ a,b\}^* \mid w\text{ has equal number of a's and b's}\}$ $\{a^n \mid n \geq 0 \} \cup \{b^n \mid n \geq 0\} \cup \{a^n b^n \mid n \geq 0\}$ $\{ a,b\}^*$
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)
|
5
views
gate2016-1
theory-of-computation
context-free-languages
normal
video-solution
0
votes
0
answers
GATE2017-1-38 Video Solution
Consider the following languages over the alphabet $\sum = \left \{ a, b, c \right \}$. Let $L_{1} = \left \{ a^{n}b^{n}c^{m}|m,n \geq 0 \right \}$ and $L_{2} = \left \{ a^{m}b^{n}c^{n}|m,n \geq 0 \right \}$. Which of the following are context-free languages? $L_{1} \cup L_{2}$ $L_{1} \cap L_{2}$ I only II only I and II Neither I nor II
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)
|
9
views
gate2017-1
theory-of-computation
context-free-languages
normal
video-solution
0
votes
0
answers
GATE2016-2-43 Video Solution
Consider the following languages: $L_{1}=\left\{a^{n}b^{m}c^{n+m}:m, n\geq 1\right\}$ $L_{2}=\left\{a^{n}b^{n}c^{2n} :n\geq 1\right\}$ Which one of the following is TRUE? Both $L_{1}$ and $L_{2}$ are context-free. $L_{1}$ is context- ... $L_{2}$ is context-free while $L_{1}$ is not context-free. Neither $L_{1}$ nor $L_{2}$ is context-free.
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)
|
8
views
gate2016-2
theory-of-computation
context-free-languages
normal
video-solution
0
votes
0
answers
GATE2017-1-37 Video Solution
Consider the context-free grammars over the alphabet $\left \{ a, b, c \right \}$ given below. $S$ and $T$ are non-terminals. $G_{1}:S\rightarrow aSb \mid T, T \rightarrow cT \mid \epsilon$ ... is Finite Not finite but regular Context-Free but not regular Recursive but not context-free
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)
|
6
views
gate2017-1
theory-of-computation
context-free-languages
identify-class-language
normal
video-solution
0
votes
0
answers
GATE2007-IT-49 Video Solution
Consider the following grammars. Names representing terminals have been specified in capital letters. $\begin{array}{llll}\hline \text{$G1$ :} & \text{stmnt} & \text{$ ... $G_1$ and $G_2$ are regular Both $G_1$ and $G_2$ are context-free but neither of them is regular
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)
|
16
views
gate2007-it
theory-of-computation
context-free-languages
normal
video-solution
0
votes
0
answers
GATE2016-2-18 Video Solution
Consider the following types of languages: $L_{1}$: Regular, $L_{2}$: Context-free, $L_{3}$: Recursive, $L_{4}$: Recursively enumerable. Which of the following is/are TRUE ? $\overline{L_{3}} \cup L_{4}$ is recursively enumerable. $\overline{L_{2}} \cup L_{3}$ ... $L_{1} \cup \overline{L_{2}}$ is context-free. I only. I and III only. I and IV only. I, II and III only.
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)
|
6
views
gate2016-2
theory-of-computation
regular-languages
context-free-languages
closure-property
normal
video-solution
0
votes
0
answers
GATE1996-2.9 Video Solution
Define a context free languages $L \in \{0, 1\}^*$, $\text{init} (L) = \{u \mid uv \in L$ for some $v$ in $\{0, 1\}^*\}$ ( in other words, $\text{init}(L)$ is the set of prefixes of $L$ ... string the set of all binary strings with exactly one more $0$ than the number of $1$'s or one more $1$ than the number of $0$'s None of the above
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)
|
9
views
gate1996
theory-of-computation
context-free-languages
normal
video-solution
0
votes
0
answers
GATE2010-40 Video Solution
Consider the languages $L1=\{0^i1^j\ \mid i \neq j\}, $ $L2=\{0^i1^j\mid i=j\},$ $L3=\{0^i1^j \mid i=2j+1\},$ $L4=\{0^i1^j \mid i\neq2j\}$ Only $L2$ is context free. Only $L2$ and $L3$ are context free. Only $L1$ and $L2$ are context free. All are context free
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)
|
4
views
gate2010
theory-of-computation
context-free-languages
identify-class-language
normal
video-solution
0
votes
0
answers
GATE2006-19 Video Solution
Let $L_1=\{0^{n+m}1^n0^m\mid n,m\geq 0 \}$, $L_2=\{0^{n+m}1^{n+m}0^m\mid n,m\geq 0\}$ and $L_3=\{0^{n+m}1^{n+m}0^{n+m}\mid n,m\geq 0\} $. Which of these languages are NOT context free? $L_1$ only $L_3$ only $L_1$ and $L_2$ $L_2$ and $L_3$
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)
|
7
views
gate2006
theory-of-computation
context-free-languages
normal
video-solution
0
votes
0
answers
GATE1992-02,xviii Video Solution
Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: If $G$ is a context free grammar and $w$ is a string of length $l$ in $L(G)$, how long is a derivation of $w$ in $G$, if $G$ is in Chomsky normal form? $2l$ $2l +1$ $2l -1$ $l$
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)
|
11
views
gate1992
theory-of-computation
context-free-languages
easy
video-solution
0
votes
0
answers
GATE2017-2-16 Video Solution
Identify the language generated by the following grammar, where $S$ is the start variable. $ S \rightarrow XY$ $ X \rightarrow aX \mid a$ $ Y \rightarrow aYb \mid \epsilon$ $\{a^mb^n \mid m \geq n, n > 0 \}$ $ \{ a^mb^n \mid m \geq n, n \geq 0 \}$ $\{a^mb^n \mid m > n, n \geq 0 \}$ $\{a^mb^n \mid m > n, n > 0 \}$
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)
|
7
views
gate2017-2
theory-of-computation
context-free-languages
video-solution
0
votes
0
answers
GATE2019-31 Video Solution
Which one of the following languages over $\Sigma=\{a, b\}$ is NOT context-free? $\{ww^R \mid w \in \{a, b\}^*\}$ $\{wa^nb^nw^R \mid w \in \{a,b\}^*, n \geq 0\}$ $\{wa^nw^Rb^n \mid w \in \{a,b\}^* , n \geq 0\}$ $\{ a^nb^i \mid i \in \{n, 3n, 5n\}, n \geq 0\}$
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)
|
10
views
gate2019
theory-of-computation
context-free-languages
video-solution
0
votes
0
answers
GATE2017-1-34 Video Solution
If $G$ is a grammar with productions $S\rightarrow SaS\mid aSb\mid bSa\mid SS\mid\epsilon$ where $S$ is the start variable, then which one of the following strings is not generated by $G$? $abab$ $aaab$ $abbaa$ $babba$
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)
|
6
views
gate2017-1
theory-of-computation
context-free-languages
normal
video-solution
0
votes
0
answers
GATE2008-IT-34 Video Solution
Consider a CFG with the following productions. $S \to AA \mid B$ $A \to 0A \mid A0 \mid 1$ $B \to 0B00 \mid 1$ $S$ is the start symbol, $A$ and $B$ ... $\{0, 1\}$ containing at least two $0$'s
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)
|
6
views
gate2008-it
theory-of-computation
context-free-languages
normal
video-solution
0
votes
0
answers
GATE2014-3-35 Video Solution
Which one of the following problems is undecidable? Deciding if a given context-free grammar is ambiguous. Deciding if a given string is generated by a given context-free grammar. Deciding if the language generated by a given context-free grammar is empty. Deciding if the language generated by a given context-free grammar is finite.
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)
|
6
views
gate2014-3
theory-of-computation
context-free-languages
decidability
normal
video-solution
0
votes
0
answers
GATE2008-IT-79 Video Solution
$A$ CFG $G$ is given with the following productions where $S$ is the start symbol, $A$ is a non-terminal and a and b are terminals. $S → aS \mid A$ $A → aAb \mid bAa \mid \epsilon$ For the string "$aabbaab$" how many steps are required to derive the string and how many parse trees are there? $6$ and $1$ $6$ and $2$ $7$ and $2$ $4$ and $2$
asked
Apr 18, 2020
in
Compiler Design
by
admin
(
573
points)
|
6
views
gate2008-it
compiler-design
context-free-languages
parsing
normal
video-solution
0
votes
0
answers
GATE2008-IT-78 Video Solution
A $CFG$ $G$ is given with the following productions where $S$ is the start symbol, $A$ is a non-terminal and $a$ and $b$ are terminals. $S \to aS \mid A$ $A \to aAb \mid bAa \mid \epsilon$ Which of the following strings is generated by the grammar above? $aabbaba$ $aabaaba$ $abababb$ $aabbaab$
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)
|
4
views
gate2008-it
theory-of-computation
normal
context-free-languages
video-solution
0
votes
0
answers
GATE2001-1.5 Video Solution
Which of the following statements is true? If a language is context free it can always be accepted by a deterministic push-down automaton The union of two context free languages is context free The intersection of two context free languages is a context free The complement of a context free language is a context free
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)
|
15
views
gate2001
theory-of-computation
context-free-languages
easy
video-solution
0
votes
0
answers
GATE1999-1.5 Video Solution
Context-free languages are closed under: Union, intersection Union, Kleene closure Intersection, complement Complement, Kleene closure
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)
|
12
views
gate1999
theory-of-computation
context-free-languages
easy
video-solution
0
votes
0
answers
GATE1995-2.20 Video Solution
Which of the following definitions below generate the same language as $L$, where $L=\{x^ny^n \text{ such that } n\geq 1 \}$? $E \rightarrow xEy\mid xy$ $x y \mid (x^+xyy^+$) $x^+y^+$ I only I and II II and III II only
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)
|
12
views
gate1995
theory-of-computation
easy
context-free-languages
video-solution
0
votes
0
answers
GATE2014-3-36 Video Solution
Consider the following languages over the alphabet $\sum = \{0, 1, c\}$ $L_1 = \left\{0^n1^n\mid n \geq 0\right\}$ $L_2 = \left\{wcw^r \mid w \in \{0,1\}^*\right\}$ ... of the string $w$. Which of these languages are deterministic Context-free languages? None of the languages Only $L_1$ Only $L_1$ and $L_2$ All the three languages
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)
|
5
views
gate2014-3
theory-of-computation
identify-class-language
context-free-languages
normal
video-solution
0
votes
0
answers
GATE2007-IT-48 Video Solution
Consider the grammar given below: $S \rightarrow x \ B \mid y \ A$ $A \rightarrow x \mid x \ S \mid y \ A \ A$ $B \rightarrow y \mid y \ S \mid x \ B \ B$ Consider the following strings. $xxyyx$ $xxyyxy$ $xyxy$ $yxxy$ $yxx$ $xyx$ Which of the above strings are generated by the grammar ? i, ii and iii ii, v and vi ii, iii and iv i, iii and iv
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)
|
3
views
gate2007-it
theory-of-computation
context-free-languages
normal
video-solution
0
votes
0
answers
GATE2005-57 Video Solution
Consider the languages: $L_1 = \left\{ww^R \mid w \in \{0, 1\}^* \right\}$ $L_2 = \left\{w\text{#}w^R \mid w \in \{0, 1\}^* \right\}$, where $\text{#}$ ... of the following is TRUE? $L_1$ is a deterministic CFL $L_2$ is a deterministic CFL $L_3$ is a CFL, but not a deterministic CFL $L_3$ is a deterministic CFL
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)
|
5
views
gate2005
theory-of-computation
context-free-languages
easy
video-solution
0
votes
0
answers
GATE1996-2.8 Video Solution
If $L_1$ and $L_2$ are context free languages and $R$ a regular set, one of the languages below is not necessarily a context free language. Which one? $L_1.L_2$ $L_1 \cap L_2$ $L_1 \cap R$ $L_1 \cup L_2$
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)
|
5
views
gate1996
theory-of-computation
context-free-languages
easy
video-solution
0
votes
0
answers
GATE2007-IT-46 Video Solution
The two grammars given below generate a language over the alphabet $\{x, y, z\}$ $G1 : S \rightarrow x \mid z \mid x \ S \mid z \ S \mid y \ B$ $B \rightarrow y \mid z \mid y \ B \mid z \ B$ ... Every $x$ is followed by at least one $y$ $G1$ : No $y$ appears after any $x$ $G2$ : Every $y$ is followed by at least one $x$
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)
|
4
views
gate2007-it
theory-of-computation
normal
context-free-languages
video-solution
0
votes
0
answers
GATE2006-IT-34 Video Solution
In the context-free grammar below, $S$ is the start symbol, $a$ and $b$ are terminals, and $\epsilon$ denotes the empty string. $S \to aSAb \mid \epsilon$ $A \to bA \mid \epsilon$ The grammar generates the language $((a + b)^* b)$ $\{a^mb^n \mid m \leq n\}$ $\{a^mb^n \mid m = n)$ $a^* b^*$
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)
|
15
views
gate2006-it
theory-of-computation
context-free-languages
normal
video-solution
Page:
1
2
next »
Quick search syntax
tags
tag:apple
author
user:martin
title
title:apple
content
content:apple
exclude
-tag:apple
force match
+apple
views
views:100
score
score:10
answers
answers:2
is accepted
isaccepted:true
is closed
isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Recent Posts
New GATEOverflow PDFs
Guidelines to users
No Recent Blog Comments
8,998
questions
3,130
answers
14,378
comments
95,816
users