later, we can repeat the argument. It follows then, by induction on the number of
times the production is applied, that
Therefore, if
.
By similar reasoning, we can show that if w ∈ L ( ) then w ∈ L (G),
completing the proof.
Theorem 6.1 is a simple and quite intuitive substitution rule: A production A
→ x 1 Bx 2 can be eliminated from a grammar if we put in its place the set of
productions in which B is replaced by all strings it derives in one step. In this
result, it is necessary that A and B be different variables. The case when A = B is
partially addressed in Exercises 23 and 24 at the end of this section.
Example 6.1
Consider G = ({A, B}, {a,b,c}, A, P) with productions
Using the suggested substitution for the variable B, we get the grammar with
productions
The new grammar is equivalent to G. The string aaabbc has the derivation
in G, and the corresponding derivation