Register

Peter Linz Edition 4 Exercise 6.1 Question 17 (Page No. 162)

226 views
1 votes
1 votes

Show that if a grammar has no $λ$-productions and no unit-productions, then the removal of useless productions by the construction of Theorem 6.2 does not introduce any such productions.

Theorem 6.2
Let $G = (V, T, S, P )$ be a context-free grammar. Then there exists an equivalent grammar $\widehat{G}=(\widehat V,\widehat{T},\widehat S, \widehat P) $ that does not contain any useless variables or productions.

User Avatar

Please log in or register to answer this question.

Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
0 answers
1
Naveen Kumar 3 asked Apr 17, 2019
186 views
Peter Linz Edition 4 Exercise 6.1 Question 18 (Page No. 162)
Justify the claim made in the proof of Theorem 6.1 that the variable $B$ can be replaced as soon as it appears.
Justify the claim made in the proof of Theorem 6.1 that the variable $B$ can be replaced as soon asit appears.
User Avatar
0 votes
0 votes
0 answers
3
Naveen Kumar 3 asked Apr 15, 2019
196 views
Peter Linz Edition 4 Exercise 6.1 Question 14 (Page No. 162)
Suppose that $G$ is a context-free grammar for which $λ ∈ L (G)$. Show that if we apply the construction in Theorem 6.3, we obtain a new grammar $\widehat{G}$ such that $L(\widehat{G} ) = L (G) –$ {$λ$}.
Suppose that $G$ is a context-free grammar for which $λ ∈ L (G)$. Show that if we apply theconstruction in Theorem 6.3, we obtain a new grammar $\widehat{G}$ such that...
User Avatar
0 votes
0 votes
1 answer
4
Naveen Kumar 3 asked Apr 15, 2019
248 views
Peter Linz Edition 4 Exercise 6.1 Question 12 (Page No. 162)
Remove $λ$-productions from the grammar with productions $S\rightarrow aSb|SS|\lambda.$ What language does the resulting grammar generate?
Remove $λ$-productions from the grammar with productions $S\rightarrow aSb|SS|\lambda.$What language does the resulting grammar generate?
User Avatar
Link Copied!