Past exam of the mathematics course of the University of Cambridge / 2021 / ii / Paper 3 / 12F / i

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 writtenwhere $|vxy|\le p$, $|vy|>0$, and replacing the subtree between the repeated variables zero, one, or several times provesThis 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^i{b}^i{a}^i:i\ge 0\}$ 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.