Theorem 6.4
Let G = (V, T, S, P) be any context-free grammar without λ-productions. Then
there exists a context-free grammar
that does not have any
unit-productions and that is equivalent to G.
Proof: Obviously, any unit-production of the form A → A can be removed from
the grammar without effect, and we need only consider A → B, where A and B
are different variables. At first sight, it may seem that we can use Theorem 6.1
directly with x 1 = x 2 = λ to replace
A → B
with
A → y 1 |y 2 |…|y n .
But this will not always work; in the special case
the unit-productions are not removed. To get around this, we first find, for each
A, all variables B such that
We can do this by drawing a dependency graph with an edge (C, D) whenever
the grammar has a unit-production C → D; then (6.4) holds whenever there is a
walk between A and B. The new grammar is generated by first putting into
all non-unit productions of P. Next, for all A and B satisfying (6.4), we add to
A → y 1 |y 2 |…|y n ,
where B → y 1 |y 2 |…|y n is the set of all rules in with B on the left. Note that
since B → y 1 |y 2 |…|y n is taken from , none of the y i can be a single variable, so
that no unit-productions are created by the last step.