P 1 ) such that V 1 contains only variables A for which
is possible. The steps in the algorithm are
1. Set V 1 to ø.
2. Repeat the following step until no more variables are added to V 1 . For every
A ∈ V for which P has a production of the form
add A to V 1 .
3. Take P 1 as all the productions in P whose symbols are all in (V 1 ∪ T).
Clearly this procedure terminates. It is equally clear that if A ∈ V 1 , then
is a possible derivation with G 1 . The remaining issue is whether
every A for which
is added to V 1 before the procedure
terminates. To see this, consider any such A and look at the partial derivation tree
corresponding to that derivation (Figure 6.2). At level k, there are only terminals,
so every variable A i at level k – 1 will be added to V 1 on the first pass through
Step 2 of the algorithm. Any variable at level k – 2 will then be added to V 1 on
the second pass through Step 2. The third time through Step 2, all variables at
level k – 3 will be added, and so on. The algorithm cannot terminate while there
are variables in the tree that are not yet in V 1 . Hence A will eventually be added
to V 1 .
Figure 6.2