Proof Of Pumping Lemma

Proof of Pumping Lemma

(a)    Suppose we have a CFL given by L. Then there is some context-free Grammar G that generates L. Suppose

1. L is infinite, hence there is no proper upper bound on the length of strings belonging to L.
2. L does not contain l.
3. G has no productions or l-productions.

There are only a finite number of variables in a grammar and the productions for each variable have finite lengths. The only way that a grammar can generate arbitrarily long strings is if one or more variables is both useful and recursive.

Suppose no variable is recursive.

Since the start symbol is nonrecursive, it must be defined only in terms of terminals and other variables. Then since those variabls are non recursive, they have to be defined in terms of terminals and still other variables and so on. After a while we run out of “other variables” while the generated string is still finite. Therefore there is an upperbond on the length of the string which can be generated from the start symbol. This contradicts our statement that the language is finite. Hence, our assumption that no variable is recursive must be incorrect.

(b) Let us 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 should have started as

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

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

This shows that derivation steps

are possible. Hence the derivation

must also be possible.

• It should be noted here 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 does not contain any l-productions or unit productions, every derivation step either introduces a terminal or increases the length of the sentential form. Since A vAx =>* , it follows that | vx| > 0.
• Finally, since uvAxy occurs in the derivation, and A vAx =>* and A w =>* are both possible, it follows that uv iwx i y also belongs to L. This completes the proof of all parts of Lemma.