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
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.