Since A was used in the derivation, the derivation must have started as

Finally, the derivation must have eliminated all variables to reach a string X in the language:

This shows that derivation steps

(Notice, by the way, that the above does not imply that A was used recursively only once. The "*" of "" could cover many uses of A, as well as other recursive variables.)

There has to be some "last" recursive step. Consider the longest strings that can be derived for v, w, and x without the use of recursion. Then there is a number m such that |vwx| < m.

Since the grammar (by hypothesis) does not contain any -productions or unit productions, every derivation step either introduces a terminal or increases the length of the sentential form. Since AvAx, it follows that |vx| > 0.

Finally, since uvAxy occurs in the derivation, and AvAx
and Aw are both
possible, it follows that uv^{i}wx^{i}y also belongs to L.

This completes the proof of all parts of lemma.

Copyright © 1996 by David Matuszek

Last modified Mar 20, 1996