Pumping lemma for context-free languages

Remarks

Take a context-free grammar for $L$ in Chomsky normal form with $k$ nonterminals and set $p = 2^k$. A parse tree of a word of length at least $p$ is binary, so it has a root-to-leaf path with more than $k$ nonterminals. So some nonterminal $A$ repeats on the lowest part of this path. The subtree under the upper $A$ yields $vxy$, the one under the lower $A$ yields $x$, and replacing one subtree by the other, or the reverse, repeatedly gives $u v^i x y^i z$. Example: $L = \set{a^n b^n c^n : n \ge 0}$ is not context-free. For $w = a^p b^p c^p$, the part $vxy$ has length at most $p$, so it meets at most two of the three blocks. Then $u v^2 x y^2 z$ either has letters out of order or has unequal block lengths, so it is not in $L$. The lemma gives only a necessary condition: some languages that are not context-free satisfy its conclusion.

Going deeper

For a student

The lemma is the context-free analogue of the pumping lemma for regular languages, where one piece is pumped instead of two. A typical proof that $L$ is not context-free picks a word depending on $p$, considers every split allowed by clauses 1 and 2, and finds an $i$ with $u v^i x y^i z \notin L$. Since the context-free languages are closed under intersection with regular languages and under homomorphisms, one often first simplifies $L$ in this way. When the lemma is too weak, Ogden's lemma, which lets one mark the important positions, often works.