Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged context-free-grammar
0
votes
0
answers
151
Peter Linz Edition 4 Exercise 6.1 Question 10 (Page No. 162)
Complete the proof of Theorem 6.3. Theorem 6.3 Let $G$ be any context-free grammar with $λ$ not in $L (G)$. Then there exists an equivalent grammar $\widehat{G}$ having no $λ$-productions.
Complete the proof of Theorem 6.3.Theorem 6.3Let $G$ be any context-free grammar with $λ$ not in $L (G)$. Then there exists an equivalent grammar $\widehat{G}$having no ...
Naveen Kumar 3
265
views
Naveen Kumar 3
asked
Apr 15, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
1
votes
1
answer
152
Peter Linz Edition 4 Exercise 6.1 Question 8 (Page No. 162)
Remove all unit-productions, all useless productions, and all λ-productions from the grammar $S\rightarrow aA|aBB,$ $A\rightarrow aaA|\lambda,$ $B\rightarrow bB|bbC,$ $C\rightarrow B.$ What language does this grammar generate?
Remove all unit-productions, all useless productions, and all λ-productions from the grammar$S\rightarrow aA|aBB,$$A\rightarrow aaA|\lambda,$$B\rightarrow bB|bbC,$$C\rig...
Naveen Kumar 3
2.4k
views
Naveen Kumar 3
asked
Apr 15, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
context-free-language
+
–
1
votes
1
answer
153
Peter Linz Edition 4 Exercise 6.1 Question 7 (Page No. 162)
Eliminate all λ-productions from $S\rightarrow AaB|aaB,$ $A\rightarrow \lambda,$ $B\rightarrow bbA|\lambda.$
Eliminate all λ-productions from$S\rightarrow AaB|aaB,$$A\rightarrow \lambda,$$B\rightarrow bbA|\lambda.$
Naveen Kumar 3
403
views
Naveen Kumar 3
asked
Apr 15, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
1
votes
2
answers
154
Peter Linz Edition 4 Exercise 6.1 Question 6 (Page No. 161)
Eliminate useless productions from $S\rightarrow a|aA|B|C,$ $A\rightarrow aB|\lambda,$ $B\rightarrow Aa,$ $C\rightarrow cCD,$ $D\rightarrow ddd.$
Eliminate useless productions from$S\rightarrow a|aA|B|C,$$A\rightarrow aB|\lambda,$$B\rightarrow Aa,$$C\rightarrow cCD,$$D\rightarrow ddd.$
Naveen Kumar 3
504
views
Naveen Kumar 3
asked
Apr 15, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
1
votes
1
answer
155
Peter Linz Edition 4 Exercise 6.1 Question 5 (Page No. 161)
Eliminate all useless productions from the grammar $S\rightarrow aS|AB,$ $A\rightarrow bA,$ $B\rightarrow AA.$ What language does this grammar generate?
Eliminate all useless productions from the grammar$S\rightarrow aS|AB,$$A\rightarrow bA,$$B\rightarrow AA.$What language does this grammar generate?
Naveen Kumar 3
377
views
Naveen Kumar 3
asked
Apr 15, 2019
Theory of Computation
peter-linz
peter-linz-edition4
context-free-grammar
context-free-language
+
–
0
votes
0
answers
156
Peter Linz Edition 4 Exercise 6.1 Question 4 (Page No. 161)
In Theorem 6.1, why is it necessary to assume that $A$ and $B$ are different variables?
In Theorem 6.1, why is it necessary to assume that $A$ and $B$ are different variables?
Naveen Kumar 3
285
views
Naveen Kumar 3
asked
Apr 15, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
0
answers
157
Peter Linz Edition 4 Exercise 6.1 Question 3 (Page No. 161)
Show that the two grammars $S\rightarrow abAB|ba,$ $A\rightarrow aaa,$ $B\rightarrow aA|bb$ and $S\rightarrow abAaA|abAbb|ba,$ $A\rightarrow aaa$ are equivalent.
Show that the two grammars$S\rightarrow abAB|ba,$$A\rightarrow aaa,$$B\rightarrow aA|bb$ and$S\rightarrow abAaA|abAbb|ba,$$A\rightarrow aaa$ ...
Naveen Kumar 3
186
views
Naveen Kumar 3
asked
Apr 15, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
0
answers
158
Peter Linz Edition 4 Exercise 6.1 Question 2 (Page No. 161)
Show a derivation tree for the string $ababbac$, using grammar with productions $A\rightarrow a|aaA|abBC,$ $B\rightarrow abbA|b.$ also show the derivation tree for grammar with productions $A\rightarrow a|aaA|ababbAc|abbc,$ $B\rightarrow abbA|b.$
Show a derivation tree for the string $ababbac$, using grammar with productions$A\rightarrow a|aaA|abBC,$$B\rightarrow abbA|b.$also show the derivation tree for grammar w...
Naveen Kumar 3
143
views
Naveen Kumar 3
asked
Apr 15, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
0
answers
159
Peter Linz Edition 4 Exercise 6.1 Question 1 (Page No. 161)
Complete the proof of Theorem 6.1 by showing that $S\overset{*}{\Rightarrow}_{\widehat{G}} w$ implies $S\overset{*}{\Rightarrow}_{G} w$. Theorem 6.1 Let $G = (V, T, S, P)$ be a context-free grammar. Suppose that $P$ ... $P$, and adding to it $A\rightarrow x_1y_1x_2|x_1y_2x_2|...|x_1y_nx_2.$ Then, $L(\widehat{G})=L(G)$.
Complete the proof of Theorem 6.1 by showing that $S\overset{*}{\Rightarrow}_{\widehat{G}} w$implies $S\overset{*}{\Rightarrow}_{...
Naveen Kumar 3
523
views
Naveen Kumar 3
asked
Apr 15, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
2
votes
1
answer
160
Peter Linz Edition 4 Exercise 5.2 Question 20 (Page No. 145)
Find a grammar equivalent to $S\rightarrow aAB, A\rightarrow bBb, B\rightarrow A|\lambda$ that satisfies the conditions of Theorem 5.2. Theorem 5.2 Suppose that $G = (V, T, S, P)$ is a context-free grammar that does not have ... algorithm which, for any $w ∈ Σ^*,$ either produces a parsing of $w$ or tells us that no parsing is possible.
Find a grammar equivalent to $S\rightarrow aAB, A\rightarrow bBb, B\rightarrow A|\lambda$ that satisfies the conditions of Theorem 5.2.Theorem 5.2Suppose that $G = (V, T,...
Naveen Kumar 3
369
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
0
answers
161
Peter Linz Edition 4 Exercise 5.2 Question 19 (Page No. 145)
Prove the following result. Let $G = (V, T, S, P )$ be a context-free grammar in which every $A ∈ V$ occurs on the left side of at most one production. Then $G$ is unambiguous.
Prove the following result. Let $G = (V, T, S, P )$ be a context-free grammar in which every $A ∈ V$ occurs on the left side of at most one production. Then $G$ is unam...
Naveen Kumar 3
210
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
ambiguous
+
–
0
votes
1
answer
162
Peter Linz Edition 4 Exercise 5.2 Question 18 (Page No. 145)
Is the string $aabbababb$ in the language generated by the grammar $S → aSS|b$? Show that the grammar with productions $S\rightarrow aAb|\lambda,$ $A\rightarrow aAb|\lambda$ is unambiguous.
Is the string $aabbababb$ in the language generated by the grammar $S → aSS|b$?Show that the grammar with productions$S\rightarrow aAb|\lambda,$$A\rightarrow aAb|\lambd...
Naveen Kumar 3
327
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
ambiguous
+
–
0
votes
1
answer
163
Peter Linz Edition 4 Exercise 5.2 Question 17 (Page No. 145)
Use the exhaustive search parsing method to parse the string $abbbbbb$ with the grammar with productions $S\rightarrow aAB,$ $A\rightarrow bBb,$ $B\rightarrow A|\lambda.$ In general, how many rounds will be needed to parse any string $w$ in this language?
Use the exhaustive search parsing method to parse the string $abbbbbb$ with the grammar with productions$S\rightarrow aAB,$$A\rightarrow bBb,$$B\rightarrow A|\lambda.$In ...
Naveen Kumar 3
406
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
parsing
+
–
0
votes
0
answers
164
Peter Linz Edition 4 Exercise 5.1 Question 27 (Page No. 135)
Let $G = (V,T,S,P)$ be a context-free grammar such that every one of its productions is of the form $A → v,$ with $|v| = k > 1.$ Show that the derivation tree for any $w ∈ L(G)$ has a height $h$ such that $\log_{k}|w|\leq h\leq \frac{(|w|-1)}{k-1}$.
Let $G = (V,T,S,P)$ be a context-free grammar such that every one of its productions is of the form $A → v,$ with $|v| = k 1.$ Show that the derivation tree for any $w...
Naveen Kumar 3
261
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
0
answers
165
Peter Linz Edition 4 Exercise 5.1 Question 26 (Page No. 135)
Find a linear grammar for the language $L=$ {$a^nb^m:n\neq m$}.
Find a linear grammar for the language $L=$ {$a^nb^m:n\neq m$}.
Naveen Kumar 3
135
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
context-free-language
+
–
0
votes
0
answers
166
Peter Linz Edition 4 Exercise 5.1 Question 25 (Page No. 135)
Prove that if $G$ is a context-free grammar, then every $w ∈ L(G)$ has a leftmost and rightmost derivation. Give an algorithm for finding such derivations from a derivation tree.
Prove that if $G$ is a context-free grammar, then every $w ∈ L(G)$ has a leftmost and rightmost derivation. Give an algorithm for finding such derivations from a deriva...
Naveen Kumar 3
163
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
context-free-language
+
–
0
votes
0
answers
167
Peter Linz Edition 4 Exercise 5.1 Question 24 (Page No. 135)
Find a context-free grammar that can generate all the production rules for context-free grammars with $T =$ {$a, b$} and $V =$ {$A, B, C$}.
Find a context-free grammar that can generate all the production rules for context-free grammars with $T =$ {$a, b$} and $V =$ {$A, B, C$}.
Naveen Kumar 3
140
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
0
answers
168
Peter Linz Edition 4 Exercise 5.1 Question 23 (Page No. 135)
Find a context-free grammar for the set of all regular expressions on the alphabet {$a, b$}.
Find a context-free grammar for the set of all regular expressions on the alphabet {$a, b$}.
Naveen Kumar 3
126
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
1
answer
169
Peter Linz Edition 4 Exercise 5.1 Question 22 (Page No. 135)
Define what one might mean by properly nested parenthesis structures involving two kinds of parentheses, say ( ) and [ ]. Intuitively, properly nested strings in this situation are ([ ]), ([[ ]])[( )], but not ([ )] or (( ]]. Using your definition, give a context-free grammar for generating all properly nested parentheses.
Define what one might mean by properly nested parenthesis structures involving two kinds of parentheses, say ( ) and [ ]. Intuitively, properly nested strings in this sit...
Naveen Kumar 3
393
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
1
answer
170
Peter Linz Edition 4 Exercise 5.1 Question 21 (Page No. 135)
Consider the derivation tree below. Find a grammar $G$ for which this is the derivation tree of the string $aab$. Then find two more sentences of $L(G)$. Find a sentence in $L(G)$ that has a derivation tree of height five or larger.
Consider the derivation tree below.Find a grammar $G$ for which this is the derivation tree of the string $aab$. Then find two more sentences of $L(G)$. Find a sentence i...
Naveen Kumar 3
612
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
1
answer
171
Peter Linz Edition 4 Exercise 5.1 Question 20 (Page No. 135)
Consider the grammar with productions $S\rightarrow aaB,$ $A\rightarrow bBb|\lambda,$ $B\rightarrow Aa.$ Show that the string $aabbabba$ is not in the language generated by this grammar.
Consider the grammar with productions$S\rightarrow aaB,$$A\rightarrow bBb|\lambda,$$B\rightarrow Aa.$Show that the string $aabbabba$ is not in the language generated by t...
Naveen Kumar 3
234
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
1
votes
1
answer
172
Peter Linz Edition 4 Exercise 5.1 Question 19 (Page No. 134)
Show a derivation tree for the string $aabbbb$ with the grammar $S\rightarrow AB|\lambda,$ $A\rightarrow aB,$ $B\rightarrow Sb.$ Give a verbal description of the language generated by this grammar.
Show a derivation tree for the string $aabbbb$ with the grammar$S\rightarrow AB|\lambda,$$A\rightarrow aB,$$B\rightarrow Sb.$Give a verbal description of the language gen...
Naveen Kumar 3
498
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
context-free-language
+
–
0
votes
1
answer
173
Peter Linz Edition 4 Exercise 5.1 Question 18 (Page No. 134)
Show that the language $L=$ {$w_1cw_2:w_1,w_2∈$ {$a,b$}$^+,w_1\neq w_2^R$}, with $Σ =$ {$a,b,c$},is context-free.
Show that the language $L=$ {$w_1cw_2:w_1,w_2∈$ {$a,b$}$^+,w_1\neq w_2^R$}, with $Σ =$ {$a,b,c$},is context-free.
Naveen Kumar 3
234
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
context-free-language
+
–
0
votes
0
answers
174
Peter Linz Edition 4 Exercise 5.1 Question 17 (Page No. 134)
Show that the complement of the language $L =$ {$a^nb^mc^k : k = n + m$} is context-free.
Show that the complement of the language $L =$ {$a^nb^mc^k : k = n + m$} is context-free.
Naveen Kumar 3
157
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
context-free-language
+
–
0
votes
1
answer
175
Peter Linz Edition 4 Exercise 5.1 Question 16 (Page No. 134)
Show that the complement of the language $L=$ {$ww^R:w∈$ {$a,b$}$^*$} is context-free.
Show that the complement of the language $L=$ {$ww^R:w∈$ {$a,b$}$^*$} is context-free.
Naveen Kumar 3
204
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
context-free-language
+
–
0
votes
1
answer
176
Peter Linz Edition 4 Exercise 5.1 Question 15 (Page No. 134)
Show that the following language is context-free. $L=$ {$uvwv^R:u,v,w∈$ {$a,b$}$^+,|u|=|w|=2$}.
Show that the following language is context-free. $L=$ {$uvwv^R:u,v,w∈$ {$a,b$}$^+,|u|=|w|=2$}.
Naveen Kumar 3
324
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
context-free-language
+
–
0
votes
1
answer
177
Peter Linz Edition 4 Exercise 5.1 Question 14 (Page No. 134)
Let $L_1$ be the language $L_1 =$ {$a^nb^mc^k : n = m$ or $m ≤ k$} and $L_2$ the language $L_2 =$ {$a^nb^mc^k : n + 2m = k$}. Show that $L_1 ∪ L_2$ is a context-free language.
Let $L_1$ be the language $L_1 =$ {$a^nb^mc^k : n = m$ or $m ≤ k$} and $L_2$ the language $L_2 =$ {$a^nb^mc^k : n + 2m = k$}. Show that $L_1 ∪ L_2$ is a context-free ...
Naveen Kumar 3
289
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
context-free-language
+
–
0
votes
1
answer
178
Peter Linz Edition 4 Exercise 5.1 Question 13 (Page No. 134)
Let $L =$ {$a^nb^n : n ≥ 0$}. (a) https://gateoverflow.in/305106/peter-linz-edition-4-exercise-5-1-question-13-a-page-no-134 (b) Show that $L^k$ is context-free for any given $k ≥ 1$. (c) Show that $\overline{L}$ and $L^*$ are context-free.
Let $L =$ {$a^nb^n : n ≥ 0$}.(a) https://gateoverflow.in/305106/peter-linz-edition-4-exercise-5-1-question-13-a-page-no-134(b) Show that $L^k$ is context-free for any g...
Naveen Kumar 3
338
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
0
answers
179
Peter Linz Edition 4 Exercise 5.1 Question 12 (Page No. 134)
Given a context-free grammar $G$ for a language $L$, show how one can create from $G$ a grammar $\widehat{G}$ so that $L(\widehat{G}$) = head (L).
Given a context-free grammar $G$ for a language $L$, show how one can create from $G$ a grammar $\widehat{G}$ so that $L(\widehat{G}$) = head (L).
Naveen Kumar 3
189
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
1
answer
180
Peter Linz Edition 4 Exercise 5.1 Question 11 (Page No. 134)
Find a context-free grammar for $Σ =$ {$a, b$} for the language $L =$ {$a^nww^Rb^n : w ∈ Σ^*, n ≥ 1$}.
Find a context-free grammar for $Σ =$ {$a, b$} for the language $L =$ {$a^nww^Rb^n : w ∈ Σ^*, n ≥ 1$}.
Naveen Kumar 3
198
views
Naveen Kumar 3
asked
Apr 14, 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
10
11
12
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register