Obviously, the resulting grammar is in Chomsky normal form. Repeated
applications of Theorem 6.1 will show that L (G 1 )= L ( ), so that
L ( ) = L (G).
This somewhat informal argument can easily be made more precise. We will
leave this to the reader.
Example 6.8
Convert the grammar with productions
to Chomsky normal form.
As required by the construction of Theorem 6.6, the grammar does not have
any λ-productions or any unit-productions.
In Step 1, we introduce new variables B a , B b , B c and use the algorithm to get