EXERCISES
1. Complete the proof of Theorem 6.1 by showing that
implies
2. In Example 6.1, show a derivation tree for the string ababbac, using both the
original and the modified grammar.
3. Show that the two grammars
and
are equivalent.
4. In Theorem 6.1, why is it necessary to assume that A and B are different
variables?
5. Eliminate all useless productions from the grammar
What language does this grammar generate?
6. Eliminate useless productions from