Show that the removal of useless productions always reduces the
complexity in this sense. What can you say about the removal of λproductions and unit-productions?
22. A context-free grammar G is said to be minimal for a given language L if
complexity (G) ≤ complexity ( ) for any generating L. Show by example
that the removal of useless productions does not necessarily produce a
minimal grammar.
* 23. Prove the following result. Let G = (V, T, S, P) be a context-free grammar.
Divide the set of productions whose left sides are some given variable (say,
A), into two disjoint subsets
where x i ,y i are in (V ∪ T) * , but A is not a prefix of any y i . Consider the
grammar
, where
and is obtained by
replacing all productions that have A on the left by
Then L (G) = L ( ).
24. Use the result of the preceding exercise to rewrite the grammar
so that it no longer has productions of the form A → Ax or B → Bx.
* 25. Prove the following counterpart of Exercise 23. Let the set of productions
involving the variable A on the left be divided into two disjoint subsets