Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged context-free-grammar
0
votes
0
answers
91
Ullman (TOC) Edition 3 Exercise 9.5 Question 1 (Page No. 418)
Let $L$ be the set of (codes for) context-free grammars $G$ such that $L(G)$ contains at least one palindrome. Show that $L$ is undecidable. Hint: Reduce PCP to $L$ by constructing, from each instance of PCP a grammar whose language contains a palindrome if and only if the PCP instance has a solution.
Let $L$ be the set of (codes for) context-free grammars $G$ such that $L(G)$ contains at least one palindrome. Show that $L$ is undecidable. Hint: Reduce PCP to $L$ by co...
admin
223
views
admin
asked
Jul 26, 2019
Theory of Computation
ullman
theory-of-computation
context-free-grammar
pcp
descriptive
+
–
0
votes
0
answers
92
Peter Linz Edition 4 Exercise 7.4 Question 9 (Page No. 204)
Give LL grammars for the following languages, assuming $Σ =$ {$a,b, c$}. (i) $L=$ {$a^nb^mc^{n+m}:n\geq0,m\geq0$} . (ii) $L=$ {$a^{n+2}b^mc^{n+m}:n\geq0,m\geq0$} . (iii) $L=$ {$a^nb^{n+2}c^{m}:n\geq0,m\gt1$} . (iv) $L=$ {$w:n_a(w)\lt n_b(w)$} . (v) $L=$ {$w:n_a(w)+n_b(w)\neq n_c(w)$} .
Give LL grammars for the following languages, assuming $Σ =$ {$a,b, c$}.(i) $L=$ {$a^nb^mc^{n+m}:n\geq0,m\geq0$} .(ii) $L=$ {$a^{n+2}b^mc^{n+m}:n\geq0,m\geq0$} .(iii) $L...
Naveen Kumar 3
377
views
Naveen Kumar 3
asked
Jun 25, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-language
context-free-grammar
+
–
1
votes
1
answer
93
Peter Linz Edition 4 Exercise 7.4 Question 8 (Page No. 204)
Let G be a context-free grammar in Greibach normal form. Describe an algorithm which, for any given k, determines whether or not G is an LL (k) grammar.
Let G be a context-free grammar in Greibach normal form. Describe an algorithm which, for anygiven k, determines whether or not G is an LL (k) grammar.
Naveen Kumar 3
270
views
Naveen Kumar 3
asked
Jun 25, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
0
answers
94
Peter Linz Edition 4 Exercise 7.4 Question 6 (Page No. 204)
Show that if G is an LL (k) grammar, then L (G) is a deterministic context-free language.
Show that if G is an LL (k) grammar, then L (G) is a deterministic context-free language.
Naveen Kumar 3
252
views
Naveen Kumar 3
asked
Jun 25, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
context-free-language
+
–
0
votes
0
answers
95
Peter Linz Edition 4 Exercise 7.4 Question 5 (Page No. 204)
Show that any LL grammar is unambiguous.
Show that any LL grammar is unambiguous.
Naveen Kumar 3
201
views
Naveen Kumar 3
asked
Jun 25, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
context-free-language
+
–
0
votes
1
answer
96
Peter Linz Edition 4 Exercise 7.4 Question 4 (Page No. 204)
Construct an LL grammar for the language L (a*ba) ∪ L (abbb*).
Construct an LL grammar for the language L (a*ba) ∪ L (abbb*).
Naveen Kumar 3
267
views
Naveen Kumar 3
asked
Jun 25, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
context-free-language
+
–
0
votes
0
answers
97
Peter Linz Edition 4 Exercise 7.4 Question 3 (Page No. 204)
Find an LL grammar for the language L = {$w : n_a (w) = n_b (w)$}.
Find an LL grammar for the language L = {$w : n_a (w) = n_b (w)$}.
Naveen Kumar 3
166
views
Naveen Kumar 3
asked
Jun 25, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
context-free-language
+
–
0
votes
1
answer
98
Peter Linz Edition 4 Exercise 7.4 Question 2 (Page No. 204)
Show that the grammar for L = {$w : n_a (w) = n_b (w)$} which is, $S\rightarrow SS,S\rightarrow \lambda,S\rightarrow aSb,S\rightarrow bSa$ is not an LL grammar.
Show that the grammar for L = {$w : n_a (w) = n_b (w)$} which is, $S\rightarrow SS,S\rightarrow \lambda,S\rightarrow aSb,S\rightarrow bSa$ is not an LL grammar.
Naveen Kumar 3
257
views
Naveen Kumar 3
asked
Jun 25, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-language
context-free-grammar
+
–
0
votes
0
answers
99
Peter Linz Edition 4 Exercise 7.4 Question 1 (Page No. 204)
Show that the grammar $S_0\rightarrow aSbS,S\rightarrow aSbS|\lambda$ is an LL grammar and that it is equivalent to the grammar $S\rightarrow SS|aSb|ab$.
Show that the grammar $S_0\rightarrow aSbS,S\rightarrow aSbS|\lambda$ is an LL grammar and that it is equivalent to the grammar $S\rightarrow SS|aSb|ab$.
Naveen Kumar 3
195
views
Naveen Kumar 3
asked
Jun 25, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
1
votes
2
answers
100
ACE Academy: Recognition of CFG
$L1 =\left \{ a^{m} b^{n} c^{p} | \left ( m \geq n \right )\text{or} \left ( n = p \right ) \right \}$ $L2 =\left \{ a^{m} b^{n} c^{p} | \left ( m \geq n \right )\text{and} \left ( n = p \right ) \right \}$ $(a)$ Both are NCFL’s $(b)$ L1 is DCFL and L2 is NCFL $(c)$ L1 is NCFL and L2 is not context-free $(d)$ Both are not context-free
$L1 =\left \{ a^{m} b^{n} c^{p} | \left ( m \geq n \right )\text{or} \left ( n = p \right ) \right \}$ $L2 =\left \{ a^{m} b^{n} c^{p} | \left ( m \geq n \right )\text{a...
Hirak
777
views
Hirak
asked
May 22, 2019
Theory of Computation
context-free-grammar
context-free-language
dcfl
+
–
2
votes
1
answer
101
ISI2018-PCB-CS4
Let the valid moves along a staircase be $U$ (one step up) and $D$ (one step down). For example, the string $s = UUDU$ represents the sequence of moves as two steps up, then one step down, and then again one step up. Suppose a person is ... returns to the base of the staircase after the final step. Show that $L$ is not regular Write a context free grammar for accepting $L$
Let the valid moves along a staircase be $U$ (one step up) and $D$ (one step down). For example, the string $s = UUDU$ represents the sequence of moves as two steps up, t...
akash.dinkar12
711
views
akash.dinkar12
asked
May 12, 2019
Theory of Computation
isi2018-pcb-cs
theory-of-computation
context-free-grammar
descriptive
+
–
0
votes
1
answer
102
Michael Sipser Edition 3 Exercise 2 Question 28 (Page No. 157)
Give unambiguous $CFG's$ for the following languages$.$ $\text{{$w\mid$ in every prefix of $w$ the number of $a’s$ is at least the number of $b’s$}}$ $\text{{$w\mid$ the number of $a’s$ and the number of $b’s$ in $w$ are equal}}$ $\text{{$w\mid$ the number of $a’s$ is at least the number of $b’s$ in $w$}}$
Give unambiguous $CFG's$ for the following languages$.$$\text{{$w\mid$ in every prefix of $w$ the number of $a’s$ is at least the number of $b’s$}}$$\text{{$w\mid$ th...
admin
337
views
admin
asked
May 4, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-grammar
+
–
0
votes
1
answer
103
Michael Sipser Edition 3 Exercise 2 Question 27 (Page No. 157)
$G$ is a natural-looking grammar for a fragment of a programming language, but $G$ is ambiguous$.$ Show that $G$ is ambiguous$.$ Give a new unambiguous grammar for the same language$.$
$G$ is a natural-looking grammar for a fragment of a programming language, but $G$ is ambiguous$.$Show that $G$ is ambiguous$.$Give a new unambiguous grammar for the same...
admin
1.4k
views
admin
asked
May 4, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-grammar
ambiguous-grammar
+
–
1
votes
1
answer
104
Michael Sipser Edition 3 Exercise 2 Question 26 (Page No. 157)
Show that if $G$ is a $CFG$ in Chomsky normal form$,$ then for any string $w\in L(G)$ of length $n\geq 1,$ exactly $2n − 1$ steps are required for any derivation of $w.$
Show that if $G$ is a $CFG$ in Chomsky normal form$,$ then for any string $w\in L(G)$ of length $n\geq 1,$ exactly $2n − 1$ steps are required for any derivation of $w....
admin
495
views
admin
asked
May 4, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-grammar
conjunctive-normal-form
proof
+
–
0
votes
1
answer
105
Michael Sipser Edition 3 Exercise 2 Question 22 (Page No. 156)
Let $C = \{x\#y \mid x, y\in\{0,1\}^{*}$ and $x\neq y\}.$ Show that $C$ is a context-free language$.$
Let $C = \{x\#y \mid x, y\in\{0,1\}^{*}$ and $x\neq y\}.$ Show that $C$ is a context-free language$.$
admin
351
views
admin
asked
May 4, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-grammar
+
–
0
votes
1
answer
106
Michael Sipser Edition 3 Exercise 2 Question 21 (Page No. 156)
Let $\Sigma = \{a,b\}.$ Give a $CFG$ generating the language of strings with twice as many $a’s$ as $b’s.$ Prove that your grammar is correct$.$
Let $\Sigma = \{a,b\}.$ Give a $CFG$ generating the language of strings with twice as many $a’s$ as $b’s.$ Prove that your grammar is correct$.$
admin
264
views
admin
asked
May 4, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-grammar
context-free-language
+
–
0
votes
0
answers
107
Michael Sipser Edition 3 Exercise 2 Question 19 (Page No. 156)
Let $CFG$ $G$ be the following grammar$.$ $S\rightarrow aSb \mid bY \mid Y a$ $Y\rightarrow bY \mid aY \mid \epsilon$ Give a simple description of $L(G)$ in English$.$ Use that description to give a $CFG$ for $\overline{L(G)},$ the complement of $L(G).$
Let $CFG$ $G$ be the following grammar$.$ $S\rightarrow aSb \mid bY \mid Y a$$Y\rightarrow bY \mid aY \mid \epsilon$Give a simple description of $L(G)$ in English$.$ Us...
admin
304
views
admin
asked
May 4, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-grammar
context-free-language
+
–
0
votes
0
answers
108
Michael Sipser Edition 3 Exercise 2 Question 15 (Page No. 156)
Give a counterexample to show that the following construction fails to prove that the class of context-free languages is closed under star. Let $A$ be a $\text{CFL}$ that is generated by the $\text{CFG}$ ... new rule $S\rightarrow SS$ and call the resulting grammar $G'.$This grammar is supposed to generate $A^{*}.$
Give a counterexample to show that the following construction fails to prove that the class of context-free languages is closed under star. Let $A$ be a $\text{CFL}$ that...
admin
375
views
admin
asked
May 4, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-language
context-free-grammar
+
–
0
votes
1
answer
109
Michael Sipser Edition 3 Exercise 2 Question 14 (Page No. 156)
Convert the following $\text{CFG}$ into an equivalent $\text{CFG}$ in Chomsky normal form,using the procedure given in $\text{Theorem 2.9.}$ $A\rightarrow BAB \mid B \mid \epsilon$ $B\rightarrow 00 \mid \epsilon$
Convert the following $\text{CFG}$ into an equivalent $\text{CFG}$ in Chomsky normal form,using the procedure given in $\text{Theorem 2.9.}$$A\rightarrow BAB \mid B \mid ...
admin
1.9k
views
admin
asked
May 4, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-grammar
conjunctive-normal-form
+
–
0
votes
1
answer
110
Michael Sipser Edition 3 Exercise 2 Question 13 (Page No. 156)
Let $G = (V, \Sigma, R, S)$ be the following grammar. $V = \{S, T, U\}; \Sigma = \{0, \#\};$ and $R$ is the set of rules$:$ $S\rightarrow TT\mid U$ $T\rightarrow 0T\mid T0\mid \#$ $U\rightarrow 0U00\mid\#$ Describe $L(G)$ in English. Prove that $L(G)$ is not regular$.$
Let $G = (V, \Sigma, R, S)$ be the following grammar. $V = \{S, T, U\}; \Sigma = \{0, \#\};$ and $R$ is the set of rules$:$$S\rightarrow TT\mid U$$T\rightarrow 0T\mid T0\...
admin
456
views
admin
asked
May 4, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-grammar
regular-language
+
–
0
votes
0
answers
111
Michael Sipser Edition 3 Exercise 2 Question 12 (Page No. 156)
Convert the $CFG$ $G$ $R\rightarrow XRX \mid S$ $S\rightarrow aT b \mid bT a$ $T\rightarrow XT X \mid X \mid\epsilon$ $X\rightarrow a \mid b$ to an equivalent $PDA,$ using the procedure given in $\text{Theorem 2.20.}$
Convert the $CFG$ $G$$R\rightarrow XRX \mid S$$S\rightarrow aT b \mid bT a$$T\rightarrow XT X \mid X \mid\epsilon$$X\rightarrow a \mid b$ to an eq...
admin
448
views
admin
asked
May 1, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-grammar
pushdown-automata
+
–
0
votes
0
answers
112
Michael Sipser Edition 3 Exercise 2 Question 8 (Page No. 155)
Show that the string the girl touches the boy with the flower has two different leftmost derivations in grammar $G_2$ on $\text{page 103.} $ Describe in English the two different meanings of this sentence.
Show that the string the girl touches the boy with the flower has two different leftmost derivations in grammar $G_2$ on $\text{page 103.} $ Describe in English the two d...
admin
289
views
admin
asked
May 1, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-language
context-free-grammar
+
–
0
votes
1
answer
113
Michael Sipser Edition 3 Exercise 2 Question 6 (Page No. 155)
Give context-free grammars generating the following languages. The set of strings over the alphabet $\{a,b\}$ with more $a's$ than $b's$ The complement of the language $\{a^{n}b^{n}\mid n\geq 0\}$ $\{w\#x\mid w^{R}$ ... $ x_{i}\in\{a,b\}^{*},$ $\text{and for some i and }$ $ j,x_{i}=x_{j}^{R}\}$
Give context-free grammars generating the following languages.The set of strings over the alphabet $\{a,b\}$ with more $a's$ than $b's$The complement of the language $\{a...
admin
816
views
admin
asked
May 1, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-language
context-free-grammar
+
–
0
votes
1
answer
114
Michael Sipser Edition 3 Exercise 2 Question 4 (Page No. 155)
Give context-free grammars that generate the following languages$.$ In all parts, the alphabet $\sum$ is $\{0,1\}.$ $\text{{w| w contains at least three 1's}}$ $\text{{w| w starts and ends with the same symbol}}$ ... $\text{{$w|w=w^{R},$that is, w is a palindrome}}$ $\text{The empty set}.$
Give context-free grammars that generate the following languages$.$ In all parts, the alphabet $\sum$ is $\{0,1\}.$$\text{{w| w contains at least three 1’s}}$$\text{{w|...
admin
3.1k
views
admin
asked
May 1, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-language
context-free-grammar
descriptive
+
–
0
votes
0
answers
115
Michael Sipser Edition 3 Exercise 2 Question 3 (Page No. 155)
Answer each part for the following context-free grammar $G.$ $R\rightarrow XRX | S$ $S\rightarrow aT b | bT a$ $T\rightarrow XT X | X | \epsilon$ $X\rightarrow a | b$ What are the variables of $G?$ What are the terminals ... $:S\overset{*}{\Rightarrow}\epsilon.$ Give a description in English of $L(G).$
Answer each part for the following context-free grammar $G.$ $R\rightarrow XRX | S$ $S\rightarrow aT b | bT a$ ...
admin
286
views
admin
asked
May 1, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-grammar
descriptive
+
–
0
votes
0
answers
116
Michael Sipser Edition 3 Exercise 2 Question 1 (Page No. 154)
Recall the $\text{CFG}$ $G_{4}$ that we gave in $\text{Example 2.4}.$ For convenience,let’s rename it’s variable with single letters as follows, $E\rightarrow E+T|T$ $T\rightarrow T\times F|F$ $F\rightarrow (E)|a$ Give parse trees and derivations for each string. $a$ $a+a$ $a+a+a$ $((a))$
Recall the $\text{CFG}$ $G_{4}$ that we gave in $\text{Example 2.4}.$ For convenience,let’s rename it’s variable with single letters as follows, ...
admin
393
views
admin
asked
Apr 30, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-grammar
parse-trees
+
–
1
votes
1
answer
117
Made Easy Test Series : Compiler Design
Consider the following CFG: $S\rightarrow Aa\mid ca$ $A\rightarrow c\mid d$ How many conflict occur in $CLR\left ( 1 \right )$ Parsing construction ? I think $LR\left ( 0 \right )$ there is $1$ conflict, but in $SLR\left ( 1 \right )orCLR\left ( 1 \right )$ there won’t be any conflict. Someone verify it.
Consider the following CFG:$S\rightarrow Aa\mid ca$$A\rightarrow c\mid d$How many conflict occur in $CLR\left ( 1 \right )$ Parsing construction ?I think $LR\left ( 0 \ri...
srestha
686
views
srestha
asked
Apr 27, 2019
Compiler Design
compiler-design
context-free-grammar
lr-parser
made-easy-test-series
descriptive
+
–
0
votes
0
answers
118
Peter Linz Edition 4 Exercise 6.3 Question 4 (Page No. 173)
Use the CYK method to determine if the string $w = aaabbbbab$ is in the language generated by the grammar $S → aSb|b$.
Use the CYK method to determine if the string $w = aaabbbbab$ is in the language generated by the grammar $S → aSb|b$.
Naveen Kumar 3
139
views
Naveen Kumar 3
asked
Apr 19, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
0
answers
119
Peter Linz Edition 4 Exercise 6.3 Question 3 (Page No. 173)
Use the approach employed in Exercise 2 to show how the CYK membership algorithm can be made into a parsing method.
Use the approach employed in Exercise 2 to show how the CYK membership algorithm can be made into a parsing method.
Naveen Kumar 3
134
views
Naveen Kumar 3
asked
Apr 19, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
0
answers
120
Peter Linz Edition 4 Exercise 6.3 Question 2 (Page No. 173)
Use the CYK algorithm to find a parsing of the string $aab$, using the grammar with productions $S\rightarrow AB,$ $A\rightarrow BB|a,$ $B\rightarrow AB|b.$
Use the CYK algorithm to find a parsing of the string $aab$, using the grammar with productions $S\rightarrow AB,$ $A\rightarrow BB|a,$ ...
Naveen Kumar 3
166
views
Naveen Kumar 3
asked
Apr 19, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
Page:
« prev
1
2
3
4
5
6
7
8
9
...
12
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register