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 contextfreelanguages
+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
theoryofcomputation
selfdoubt
pushdownautomata
contextfreelanguages
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
theoryofcomputation
contextfreelanguages
contextsensitivelanguages
+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
pumpinglemma
contextfreelanguages
0
votes
0
answers
TOC(self doubtclassification 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 illdefined 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
theoryofcomputation
pumpinglemma
contextfreelanguages
contextsensitivelanguages
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
theoryofcomputation
contextfreelanguages
+1
vote
1
answer
pushdown automata #CFL
Is the following language contextfree language(CFL) or not? If yes, then is it DeterministicCFL (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
theoryofcomputation
pushdownautomata
contextfreelanguages
0
votes
0
answers
Peter Linz Exercise8.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
theoryofcomputation
peterlinz
contextfreelanguages
0
votes
0
answers
Peter Linz Theory of Computation Exercise 5.1 Question15
asked
Jun 11, 2020
in
Theory of Computation
by
aditi19
(
43
points)

24
views
theoryofcomputation
peterlinz
contextfreelanguages
0
votes
0
answers
GATE201835 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 contextfree? 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
theoryofcomputation
identifyclasslanguage
contextfreelanguages
normal
videosolution
0
votes
0
answers
GATE2016142 Video Solution
Consider the following contextfree 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
gate20161
theoryofcomputation
contextfreelanguages
normal
videosolution
0
votes
0
answers
GATE2017110 Video Solution
Consider the following contextfree 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
gate20171
theoryofcomputation
contextfreelanguages
normal
videosolution
0
votes
0
answers
GATE2015332 Video Solution
Which of the following languages are contextfree? $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
gate20153
theoryofcomputation
contextfreelanguages
normal
videosolution
0
votes
0
answers
GATE200351 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
theoryofcomputation
contextfreelanguages
normal
videosolution
0
votes
0
answers
GATE200912, ISRO201637 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
theoryofcomputation
contextfreelanguages
easy
isro2016
videosolution
0
votes
0
answers
GATE2016116 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
gate20161
theoryofcomputation
contextfreelanguages
normal
videosolution
0
votes
0
answers
GATE2017138 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 contextfree 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
gate20171
theoryofcomputation
contextfreelanguages
normal
videosolution
0
votes
0
answers
GATE2016243 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 contextfree. $L_{1}$ is context ... $L_{2}$ is contextfree while $L_{1}$ is not contextfree. Neither $L_{1}$ nor $L_{2}$ is contextfree.
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)

8
views
gate20162
theoryofcomputation
contextfreelanguages
normal
videosolution
0
votes
0
answers
GATE2017137 Video Solution
Consider the contextfree grammars over the alphabet $\left \{ a, b, c \right \}$ given below. $S$ and $T$ are nonterminals. $G_{1}:S\rightarrow aSb \mid T, T \rightarrow cT \mid \epsilon$ ... is Finite Not finite but regular ContextFree but not regular Recursive but not contextfree
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)

6
views
gate20171
theoryofcomputation
contextfreelanguages
identifyclasslanguage
normal
videosolution
0
votes
0
answers
GATE2007IT49 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 contextfree but neither of them is regular
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)

16
views
gate2007it
theoryofcomputation
contextfreelanguages
normal
videosolution
0
votes
0
answers
GATE2016218 Video Solution
Consider the following types of languages: $L_{1}$: Regular, $L_{2}$: Contextfree, $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 contextfree. 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
gate20162
theoryofcomputation
regularlanguages
contextfreelanguages
closureproperty
normal
videosolution
0
votes
0
answers
GATE19962.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
theoryofcomputation
contextfreelanguages
normal
videosolution
0
votes
0
answers
GATE201040 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
theoryofcomputation
contextfreelanguages
identifyclasslanguage
normal
videosolution
0
votes
0
answers
GATE200619 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
theoryofcomputation
contextfreelanguages
normal
videosolution
0
votes
0
answers
GATE199202,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
theoryofcomputation
contextfreelanguages
easy
videosolution
0
votes
0
answers
GATE2017216 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
gate20172
theoryofcomputation
contextfreelanguages
videosolution
0
votes
0
answers
GATE201931 Video Solution
Which one of the following languages over $\Sigma=\{a, b\}$ is NOT contextfree? $\{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
theoryofcomputation
contextfreelanguages
videosolution
0
votes
0
answers
GATE2017134 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
gate20171
theoryofcomputation
contextfreelanguages
normal
videosolution
0
votes
0
answers
GATE2008IT34 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
gate2008it
theoryofcomputation
contextfreelanguages
normal
videosolution
0
votes
0
answers
GATE2014335 Video Solution
Which one of the following problems is undecidable? Deciding if a given contextfree grammar is ambiguous. Deciding if a given string is generated by a given contextfree grammar. Deciding if the language generated by a given contextfree grammar is empty. Deciding if the language generated by a given contextfree grammar is finite.
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)

6
views
gate20143
theoryofcomputation
contextfreelanguages
decidability
normal
videosolution
0
votes
0
answers
GATE2008IT79 Video Solution
$A$ CFG $G$ is given with the following productions where $S$ is the start symbol, $A$ is a nonterminal 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
gate2008it
compilerdesign
contextfreelanguages
parsing
normal
videosolution
0
votes
0
answers
GATE2008IT78 Video Solution
A $CFG$ $G$ is given with the following productions where $S$ is the start symbol, $A$ is a nonterminal 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
gate2008it
theoryofcomputation
normal
contextfreelanguages
videosolution
0
votes
0
answers
GATE20011.5 Video Solution
Which of the following statements is true? If a language is context free it can always be accepted by a deterministic pushdown 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
theoryofcomputation
contextfreelanguages
easy
videosolution
0
votes
0
answers
GATE19991.5 Video Solution
Contextfree 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
theoryofcomputation
contextfreelanguages
easy
videosolution
0
votes
0
answers
GATE19952.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
theoryofcomputation
easy
contextfreelanguages
videosolution
0
votes
0
answers
GATE2014336 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 Contextfree 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
gate20143
theoryofcomputation
identifyclasslanguage
contextfreelanguages
normal
videosolution
0
votes
0
answers
GATE2007IT48 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
gate2007it
theoryofcomputation
contextfreelanguages
normal
videosolution
0
votes
0
answers
GATE200557 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
theoryofcomputation
contextfreelanguages
easy
videosolution
0
votes
0
answers
GATE19962.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
theoryofcomputation
contextfreelanguages
easy
videosolution
0
votes
0
answers
GATE2007IT46 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
gate2007it
theoryofcomputation
normal
contextfreelanguages
videosolution
0
votes
0
answers
GATE2006IT34 Video Solution
In the contextfree 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
gate2006it
theoryofcomputation
contextfreelanguages
normal
videosolution
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