For every context-free grammar G with λ ∉ L (G), there exists an equivalent
grammar in Greibach normal form.
EXERCISES
1. Provide the details of the proof of Theorem 6.6.
2. Convert the grammar
into Chomsky normal form.
3. Transform the grammar
into Chomsky
normal form.
4. Transform the grammar with productions
into Chomsky normal form.
5. Convert the grammar
into Chomsky normal form.
6. Let G = (V, T, S, P) be any context-free grammar without any λ-productions
or unit-productions. Let k be the maximum number of symbols on the right
of any production in P. Show that there is an equivalent grammar in
Chomsky normal form with no more than
production rules.
7. Draw the dependency graph for the grammar in Exercise 4.
8. A linear language is one for which there exists a linear grammar (for a
definition, see Example 3.14). Let L be any linear language not containing λ.