In the second part of the construction, we get the final answer from G 1 .
We draw the variable dependency graph for G 1 and from it find all variables that
can not be reached from S. These are removed from the variable set, as are the
productions involving them. We can also eliminate any terminal that does not
occur in some useful production. The result is the grammar
.
Because of the construction, does not contain any useless symbols or
productions. Also, for each ω ∈ L (G) we have a derivation
Since the construction of retains A and all associated productions, we have
everything needed to make the derivation
The grammar is constructed from G by the removal of productions, so that
Consequently
Putting the two results together, we see
that G and are equivalent.
Removing λ-Productions