Let L be an infinite context-free language. Then there exists some positive
integer m such that any ω ε L with |ω| ≥ m can be decomposed as
with
and
such that
for all i = 0,1, 2,…. This is known as the pumping lemma for context-free
languages.
Proof: Consider the language L - {λ}, and assume that we have for it a grammar
G without unit-productions or λ-productions. Since the length of the string on the
right side of any production is bounded, say by k, the length of the derivation of
any ω ε L must be at least |ω|/k. Therefore, since L is infinite, there exist
arbitrarily long derivations and corresponding derivation trees of arbitrary
height.
Consider now such a high derivation tree and some sufficiently long path
from the root to a leaf. Since the number of variables in G is finite, there must be
some variable that repeats on this path, as shown schematically in Figure 8.1.
Corresponding to the derivation tree in Figure 8.1, we have the derivation
where u, v, x, y, and z are all strings of terminals. From the above we see that and
and
, so all the strings uv i xy i z, i=0,1,2 can be generated by
the grammar and are therefore in L. Furthermore, in the derivations
and
we can assume that no variable repeats. To see this, look at the
sketch of the derivation tree in Figure 8.1. In the subtree T 5 no variable repeats;
otherwise we could just apply the argument to this repeating variable. Similarly,
we can assume that no variable repeats in the subtrees T 3 and T 4 . Therefore, the