[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

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

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

S derives uAy derives uvAxy derives uvwxy = X

This shows that derivation steps

A derives vAx
and
A derives w
are possible. Hence the derivation
A derives vwx
must also be possible.

(Notice, by the way, that the above does not imply that A was used recursively only once. The "*" of "derives" 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 empty string-productions or unit productions, every derivation step either introduces a terminal or increases the length of the sentential form. Since AderivesvAx, it follows that |vx| > 0.

Finally, since uvAxy occurs in the derivation, and AderivesvAx and Aderivesw are both possible, it follows that uviwxiy also belongs to L.

This completes the proof of all parts of lemma.


Copyright 1996 by David Matuszek
Last modified Mar 20, 1996