Next we want to eliminate the variables that cannot be reached from the start
variable. For this, we can draw a dependency graph for the variables.
Dependency graphs are a way of visualizing complex relationships and are
found in many applications. For context-free grammars, a dependency graph has
its vertices labeled with variables, with an edge between vertices C and D if and
only if there is a production of the form
C → xD y .
A dependency graph for V 1 is shown in Figure 6.1. A variable is useful only if
there is a path from the vertex labeled S to the vertex labeled with that variable.
In our case, Figure 6.1 shows that B is useless. Removing it and the affected
productions and terminals, we are led to the final answer
, and productions
The formalization of this process leads to a general construction and the
corresponding theorem.
Figure 6.1
Theorem 6.2
Let G = (V, T, S, P) be a context-free grammar. Then there exists an equivalent
grammar
that does not contain any useless variables or
productions.
Proof: The grammar can be generated from G by an algorithm consisting of
two parts. In the first part we construct an intermediate grammar G 1 = (V 1 , T 2 , S,