[Overview] [Previous] [Next]

Proving the Pumping Lemma, Part II

Consider a string X belonging to L. If X is sufficiently long, then the derivation of X must have involved recursive use of some variable A.

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

uAy for some values of u and y. Since A was used recursively, the derivation must have continued as S

uAy

uvAxy

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

uAy

uvAxy

uvwxy = X

This shows that derivation steps

vAx and A

w are possible. Hence the derivation A

vwx must also be possible.

(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ⁱwxⁱy also belongs to L.

This completes the proof of all parts of lemma.