= Solution
A <parse tree> has the start variable at its root; the ordered children of a variable spell the right side of the production used at that occurrence, and its leaves, read left to right, spell the derived word.
For a grammar in <Chomsky normal form> with $r$ variables, take pumping length $p=2^r$. A parse tree for a word of length at least $p$ has a root-to-leaf path containing one variable twice. The yield can therefore be written
$$
w=uvxyz,
$$
where $|vxy|\leq p$, $|vy|>0$, and replacing the subtree between the repeated variables zero, one, or several times proves
$$
uv^ixy^iz\in L\qquad(i\geq0).
$$
This is the <pumping lemma for context-free languages>. Without Chomsky normal form but with no epsilon or unit productions, use the maximum production length to choose a larger exponential $p$; bounded branching and the same repeated-variable argument apply.
The language $\{a^ib^ia^i:i\geq0\}$ is not context free. A pumped window of bounded length cannot alter all three long blocks equally, so pumping breaks one of the required equalities.
Back to article page
