Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged context-free-language
3
votes
2
answers
571
toc
$L1$ is a Context free language (CFL), $L2$ is a Deterministic Context free language (DCFL) and , $L = L1 \cap\overline{L2}$ then $L$ is a) Need not be CFL b) not CFL c)DCFL
$L1$ is a Context free language (CFL), $L2$ is a Deterministic Context free language (DCFL)and , $L = L1 \cap\overline{L2}$then $L$ isa) Need not be CFLb) not CFLc)DCFL
srestha
743
views
srestha
asked
Dec 2, 2015
Theory of Computation
context-free-language
closure-property
+
–
1
votes
1
answer
572
TOC question from virtual gate
Given answer: A Please explain
Given answer: APlease explain
shikharV
785
views
shikharV
asked
Nov 24, 2015
Theory of Computation
theory-of-computation
finite-automata
context-free-language
+
–
1
votes
0
answers
573
Context free grammar
Write a CFG for language L= {a m b n c p d q | m +n = p + q }
Write a CFG for language L= {a m b n c p d q | m +n = p + q }
priti
465
views
priti
asked
Nov 23, 2015
Theory of Computation
context-free-language
+
–
1
votes
3
answers
574
toc
how to approach $L=\{a^mb^nc^pd^q\ |\ m+n=p+q \}$ give grammar for it???
how to approach$L=\{a^mb^nc^pd^q\ |\ m+n=p+q \}$give grammar for it???
ManojK
615
views
ManojK
asked
Nov 19, 2015
Theory of Computation
theory-of-computation
context-free-language
+
–
3
votes
1
answer
575
#Toc
I read some where that if thier is one comparision at any time then only CFL otherwise CSL? plz give proof.
I read some where that if thier is one comparision at any time then only CFL otherwise CSL?plz give proof.
Prashant.
550
views
Prashant.
asked
Nov 18, 2015
Theory of Computation
context-free-language
+
–
3
votes
0
answers
576
What should be answers of Question 14, 15 and 16 and Why ??
Common Data for Q14,15 &16 is given below: Ram takes two context-free languages $L_1$ and $L_2$ a). He concatenates $L_1 $ and $L_2$ to obtain a new set $L_3$. b). He takes the complement of $L_3$ to obtain a set $L_4$ c). ... is a). recursive b). csl that is not finite c). cfl that may regular d). r.e. set that is never finite.
Common Data for Q14,15 &16 is given below: Ram takes two context-free languages $L_1$ and $L_2$ a). He concatenates $L_1 $ and $L_2$ to obtain a new set $L_3$.b). He take...
Payal Rastogi
580
views
Payal Rastogi
asked
Nov 2, 2015
Theory of Computation
theory-of-computation
regular-language
context-free-language
context-sensitive
+
–
8
votes
3
answers
577
How is the complement of Language L is Context free ??
The complement of the language $L$ containing an equal number of $a's$,$b's$ and $c's$ is (a) regular (b) context free (c) context sensitive but not context free (d) recursive and not a cfl.
The complement of the language $L$ containing an equal number of $a's$,$b's$ and $c's$ is (a) regular(b) context free(c) context sensitive but not context free(d) recursi...
Payal Rastogi
7.1k
views
Payal Rastogi
asked
Nov 2, 2015
Theory of Computation
theory-of-computation
context-free-language
context-sensitive
+
–
2
votes
4
answers
578
Which of the language accepted by the following PDA ??
Payal Rastogi
3.5k
views
Payal Rastogi
asked
Nov 2, 2015
Theory of Computation
theory-of-computation
context-free-language
+
–
1
votes
1
answer
579
Unambiguous CFL which is not DCFL
Give an example of Unambiguous CFL which is not DCFL .
Give an example of Unambiguous CFL which is not DCFL .
Himanshu1
991
views
Himanshu1
asked
Nov 2, 2015
Theory of Computation
theory-of-computation
context-free-language
dcfl
+
–
1
votes
1
answer
580
Is the grammar S$\rightarrow$ϵ empty?
Is the grammar S$\rightarrow$ϵ empty?
Is the grammar S$\rightarrow$ϵ empty?
monanshi
332
views
monanshi
asked
Oct 25, 2015
Theory of Computation
theory-of-computation
grammar
context-free-language
+
–
2
votes
1
answer
581
What is the rank of the non-terminal B in the following context free grammar?
Consider the following CFG $S \to AB$ $A \to aBc \mid aB \mid a$ $B \to bDe \mid f \mid CD$ $C \to Dg \mid h$ $D \to g$ The rank of the non-terminal $B$ is __________
Consider the following CFG$S \to AB$$A \to aBc \mid aB \mid a$$B \to bDe \mid f \mid CD$$C \to Dg \mid h$$D \to g$The rank of the non-terminal $B$ is __________
ayushigupta
2.1k
views
ayushigupta
asked
Oct 17, 2015
Theory of Computation
context-free-language
rank-of-nonterminal
+
–
21
votes
3
answers
582
TIFR CSE 2010 | Part B | Question: 25
Which of the following problems is decidable? (Here, CFG means context free grammar and CFL means context free language.) Given a CFG $G$, find whether $L(G) = R$, where $R$ is regular set. Given a CFG $G$, find whether $L(G) = \{\}$. Find whether ... whether CFG $G_1$ and CFG $G_2$ generate the same language, i.e, $L\left (G_1 \right ) = L\left (G_2 \right)$.
Which of the following problems is decidable? (Here, CFG means context free grammar and CFL means context free language.)Given a CFG $G$, find whether $L(G) = R$, where $...
makhdoom ghaya
4.8k
views
makhdoom ghaya
asked
Oct 6, 2015
Theory of Computation
tifr2010
theory-of-computation
context-free-language
decidability
+
–
2
votes
1
answer
583
give explanation..???
focus _GATE
635
views
focus _GATE
asked
Oct 4, 2015
Theory of Computation
context-free-language
+
–
5
votes
2
answers
584
Context free or not ?
$L = \{ a^i b^j c^k d^l \mid i+k=j+l \}$ Is L context free? If yes, then draw PDA. If no, why?
$L = \{ a^i b^j c^k d^l \mid i+k=j+l \}$Is L context free? If yes, then draw PDA. If no, why?
anonymous
3.8k
views
anonymous
asked
Aug 22, 2015
Theory of Computation
context-free-language
pushdown-automata
+
–
44
votes
2
answers
585
GATE CSE 2015 Set 3 | Question: 32
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
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^...
go_editor
14.9k
views
go_editor
asked
Feb 15, 2015
Theory of Computation
gatecse-2015-set3
theory-of-computation
context-free-language
normal
+
–
5
votes
1
answer
586
Find the grammar that generates inherently ambiguous context free language.
Vikrant Singh
2.6k
views
Vikrant Singh
asked
Jan 27, 2015
Theory of Computation
context-free-language
theory-of-computation
+
–
4
votes
2
answers
587
toc
Let $L_1 = \{a^nb^mc^n \mid m,n \geq 0 \}$ and $L_2 = \{a^nc^n \mid n \geq 0 \}$. Both $L_1$ and $L_2$ are context free languages. if $L = ( L_1 - L_2 )$ then $L$ is ____. a. Finite Language b. Regular language c. DCFL d. Not DCFL
Let $L_1 = \{a^nb^mc^n \mid m,n \geq 0 \}$ and $L_2 = \{a^nc^n \mid n \geq 0 \}$. Both $L_1$ and $L_2$ are context free languages. if $L = ( L_1 - L_2 )$ then $L$ is ___...
Vikrant Singh
1.7k
views
Vikrant Singh
asked
Jan 27, 2015
Theory of Computation
theory-of-computation
context-free-language
+
–
4
votes
2
answers
588
Whether given CFL is Regular is Decidable?
Which of the following are True? $S1$: Every NFA can be converted to equivalent PDA $S2$: Whether a given CFL is Regular is decidable. 1. $S1$ 2. $S2$ 3. Both 4. None
Which of the following are True?$S1$: Every NFA can be converted to equivalent PDA$S2$: Whether a given CFL is Regular is decidable.1. $S1$ ...
Vikrant Singh
3.8k
views
Vikrant Singh
asked
Jan 18, 2015
Theory of Computation
theory-of-computation
context-free-language
decidability
+
–
4
votes
4
answers
589
is it context free?
is it cfl L = { a^n b^n c^m | n>=1 , m=2n } ? i did like for stack push and pop " a & b " are coverd and later we are having stack empty? can we write this language as a^n b^n c^2n ?
is it cfl L = { a^n b^n c^m | n>=1 , m=2n } ?i did like for stack push and pop " a & b " are coverd and later we are having stack empty? can we write this language ...
rajsh3kar
4.5k
views
rajsh3kar
asked
Nov 28, 2014
Theory of Computation
theory-of-computation
context-free-language
+
–
34
votes
5
answers
590
GATE IT 2006 | Question: 34
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^*$
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 \e...
Ishrat Jahan
7.9k
views
Ishrat Jahan
asked
Oct 31, 2014
Theory of Computation
gateit-2006
theory-of-computation
context-free-language
normal
+
–
23
votes
3
answers
591
GATE IT 2006 | Question: 4
In the context-free grammar below, $S$ is the start symbol, $a$ and $b$ are terminals, and $\epsilon$ denotes the empty string $S \rightarrow aSa \mid bSb \mid a \mid b \mid \epsilon$ Which of the following strings is NOT generated by the grammar? $aaaa$ $baba$ $abba$ $babaaabab$
In the context-free grammar below, $S$ is the start symbol, $a$ and $b$ are terminals, and $\epsilon$ denotes the empty string$S \rightarrow aSa \mid bSb \mid a \mid b \m...
Ishrat Jahan
3.7k
views
Ishrat Jahan
asked
Oct 31, 2014
Theory of Computation
gateit-2006
theory-of-computation
context-free-language
easy
+
–
67
votes
3
answers
592
GATE IT 2007 | Question: 49
Consider the following grammars. Names representing terminals have been specified in capital letters. ... $G_1$ and $G_2$ are regular Both $G_1$ and $G_2$ are context-free but neither of them is regular
Consider the following grammars. Names representing terminals have been specified in capital letters.$$\begin{array}{llll}\hline \text{$G1$ :} & \text{stmnt} & \text{$\...
Ishrat Jahan
12.6k
views
Ishrat Jahan
asked
Oct 30, 2014
Theory of Computation
gateit-2007
theory-of-computation
context-free-language
normal
+
–
27
votes
2
answers
593
GATE IT 2007 | Question: 48
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
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...
Ishrat Jahan
7.4k
views
Ishrat Jahan
asked
Oct 30, 2014
Theory of Computation
gateit-2007
theory-of-computation
context-free-language
normal
+
–
25
votes
5
answers
594
GATE IT 2007 | Question: 46
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$
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$ ...
Ishrat Jahan
5.6k
views
Ishrat Jahan
asked
Oct 29, 2014
Theory of Computation
gateit-2007
theory-of-computation
normal
context-free-language
+
–
39
votes
4
answers
595
GATE IT 2008 | Question: 78
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$
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 ...
Ishrat Jahan
8.2k
views
Ishrat Jahan
asked
Oct 29, 2014
Compiler Design
gateit-2008
parsing
normal
context-free-language
+
–
44
votes
7
answers
596
GATE IT 2008 | Question: 34
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
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$ are non-terminals and 0 an...
Ishrat Jahan
14.8k
views
Ishrat Jahan
asked
Oct 28, 2014
Theory of Computation
gateit-2008
theory-of-computation
context-free-language
normal
+
–
44
votes
3
answers
597
GATE CSE 1996 | Question: 2.9
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
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...
Kathleen
10.1k
views
Kathleen
asked
Oct 9, 2014
Theory of Computation
gate1996
theory-of-computation
context-free-language
normal
+
–
23
votes
6
answers
598
GATE CSE 1996 | Question: 2.8
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$
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...
Kathleen
6.2k
views
Kathleen
asked
Oct 9, 2014
Theory of Computation
gate1996
theory-of-computation
context-free-language
easy
+
–
32
votes
8
answers
599
GATE CSE 1995 | Question: 2.20
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
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^+...
Kathleen
10.4k
views
Kathleen
asked
Oct 8, 2014
Theory of Computation
gate1995
theory-of-computation
easy
context-free-language
+
–
40
votes
1
answer
600
GATE CSE 2010 | Question: 40
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
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$ ...
go_editor
11.7k
views
go_editor
asked
Sep 30, 2014
Theory of Computation
gatecse-2010
theory-of-computation
context-free-language
identify-class-language
normal
+
–
Page:
« prev
1
...
15
16
17
18
19
20
21
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register