Register

Recent questions tagged context-free-grammar

2.9k
views
1 answers
2 votes
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?
User Avatar
432
views
1 answers
1 votes
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.$
User Avatar
565
views
2 answers
2 votes
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.$
User Avatar
396
views
1 answers
1 votes
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?
User Avatar
295
views
0 answers
0 votes
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?
User Avatar
191
views
0 answers
0 votes
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.
User Avatar
154
views
0 answers
0 votes
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.$
User Avatar
557
views
0 answers
0 votes
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$ ... adding to it $A\rightarrow x_1y_1x_2|x_1y_2x_2|...|x_1y_nx_2.$Then, $L(\widehat{G})=L(G)$.
User Avatar
390
views
1 answers
2 votes
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$ ... either produces a parsing of $w$ or tells us that no parsing is possible.
User Avatar
243
views
0 answers
0 votes
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.
User Avatar
350
views
1 answers
0 votes
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.
User Avatar
422
views
1 answers
0 votes
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.$ ... many rounds will be needed to parse any string $w$ in this language?
User Avatar
286
views
0 answers
0 votes
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.$ ... $\log_{k}|w|\leq h\leq \frac{(|w|-1)}{k-1}$.
User Avatar
148
views
0 answers
0 votes
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$}.
User Avatar
173
views
0 answers
0 votes
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.
User Avatar
156
views
0 answers
0 votes
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$}.
User Avatar
134
views
0 answers
0 votes
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$}.
User Avatar
445
views
1 answers
0 votes
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 ... definition, give a context-free grammar for generating all properly nested parentheses.
User Avatar
668
views
1 answers
0 votes
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.
User Avatar
277
views
1 answers
0 votes
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.
User Avatar
561
views
1 answers
1 votes
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.
User Avatar
248
views
1 answers
0 votes
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.
User Avatar
163
views
0 answers
0 votes
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.
User Avatar
225
views
1 answers
0 votes
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.
User Avatar
351
views
1 answers
0 votes
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$}.
User Avatar
316
views
1 answers
0 votes
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.
User Avatar
371
views
1 answers
0 votes
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.
User Avatar
200
views
0 answers
0 votes
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).
User Avatar
258
views
2 answers
0 votes
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$}.
User Avatar
263
views
0 answers
0 votes
Peter Linz Edition 4 Exercise 5.1 Question 10 (Page No. 134)
Find a context-free grammar for $head (L)$, where $L$ is the language $L =$ {$a^nb^m : n ≤ m + 3$}. Forthe definition of $head$ see Exercise 18, Section 4.1.
User Avatar
Page: