2, introduce new variables Ba for each a T. For each production of P in the
form (6.5) we put into P 1 the production
A → C 1 C 2 …C n ,
where
C i = x i if x i is in V,
and
C i = B a if x i = a.
For every B a we also put into P 1 the production
B a → a.
This part of the algorithm removes all terminals from productions whose right
side has length greater than one, replacing them with newly introduced variables.
At the end of this step we have a grammar G 1 all of whose productions have the
form
or
where C i V 1 .
It is an easy consequence of Theorem 6.1 that
L (G 1 ) = L (G).
Step 2: In the second step, we introduce additional variables to reduce the length
of the right sides of the productions where necessary. First we put all productions
of the form (6.6) as well as all the productions of the form (6.7) with n = 2 into
. For n ≥ 2, we introduce new variables D 1 , D 2 ,…and put into the
productions