The pumping lemma is pigeonhole on trees

The pumping lemma for context-free languages is taught as a spell. For any context-free language there is a length p such that any string longer than p can be split into five pieces, u v w x y, with v and x not both empty, v w x no longer than p, and every string u v^i w x^i y also in the language. Students memorise the five letters, apply the spell to a^n b^n c^n, and never quite believe it. I did not believe it either until the proof for my paper on the limits of context-free recognition forced me to draw it, at which point it stopped being a spell and became a fact about trees that a first-year student can see.

One observation

Here is the whole lemma. Take a grammar in Chomsky normal form with V nonterminals. Every internal node of a parse tree has at most two children, so a tree of height h has at most 2 to the h leaves. Turn that around: a string of length more than 2 to the V has a parse tree of height more than V, which means some root-to-leaf path has more than V internal nodes, which means, by the pigeonhole principle, some nonterminal appears twice on that path.

Call that nonterminal A. The lower A spans a substring w. The upper A spans a larger substring v w x. Because both are the same nonterminal, the subtree under the upper A can be replaced by the subtree under the lower A, which deletes v and x, or the subtree under the lower A can be replaced by a copy of the subtree under the upper A, which duplicates v and x. Do that i times and you get u v^i w x^i y, and every one of those strings has a valid parse tree, so every one is in the language. That is the lemma. The five letters are the pieces of the string that the two A nodes cut it into, and p is 2 to the power V plus one, the length at which the tree is guaranteed to be tall enough.

Two details in that argument are the ones students trip on, and both are visible in the drawing. The condition that v and x are not both empty comes from choosing the lowest pair of repeated A nodes, so that the upper A really does span more than the lower one; a pair with nothing between them would pump nothing. The condition that v w x is no longer than p comes from the same choice: the subtree under the upper A is itself short enough not to contain a repeat below it, so its leaves number at most 2 to the V. Neither is a separate fact to memorise. Both are where you put your finger on the tree.

Seen that way, the famous proof that a^n b^n c^n is not context-free is two lines. If it were, a long enough string would have a repeated nonterminal, and pumping it would add copies of v and x. But v and x are two substrings of a string with three blocks, so at most two of the three letters get more copies, and the counts stop matching. A grammar with no memory beyond its finite set of nonterminals cannot keep three counts in step, because the only way it keeps any count is by nesting, and nesting pairs things.

The tall tree test

For anything I want to show is not context-free, the working form of the lemma is what I call the tall tree test. Find a family of strings that, in any grammar for the language, must have parse trees taller than the number of nonterminals. Then show that duplicating the repeated subtree breaks something the language requires: a count that must match, or a copy that must be exact. The five letters never have to be named. The tree does the work.

The test also makes the lemma's limits obvious, which the spell version hides. The lemma says every long string in a context-free language can be pumped. It does not say every language in which every long string can be pumped is context-free; the implication runs one way. There are non-context-free languages that pass the pumping test, and that is why Ogden's lemma exists, which lets you mark positions and insist that the pumped part includes some of them. In the tree picture Ogden's lemma is the same pigeonhole with the path chosen to pass through the marked leaves. Nothing new is happening; the argument is being aimed.

The number in the lemma is useless, and that is fine

The pumping length p is 2 to the power of the nonterminal count plus one, and it is worth computing once to see how useless it is as a practical test. A tidy grammar for JSON, binarised, has a few dozen nonterminals; its pumping length is in the billions of characters. A grammar induced from the Penn Treebank sample I used in another post has 707 nonterminals, and its pumping length is 2 to the 708, a number with more than two hundred digits.

Nobody will ever test a string of that length, and nobody needs to. The number is there to make the existence claim true, and existence is all a proof requires. A student who worries that the pumping length is impractical has confused a proof with a procedure. The lemma is not a way of checking strings; it is a way of showing that no grammar can exist, and for that one tall tree is enough.

Copy or count

The applied version of the test, the one I use when someone asks whether a format can be described by a context-free grammar, is a rule I call copy or count. If the format requires an unbounded exact copy, one substring repeated verbatim elsewhere with no bound on its length, it fails the test. If it requires three or more counts to match, it fails. If it requires only pairs to match, nested, it may pass.

The XML case surprises people, and it is the best example because everyone has parsed XML with a context-free-looking parser. An opening tag with an arbitrary name must be closed by a tag with the same name, and the name is unbounded: that is an exact copy, the language w w in disguise, and no context-free grammar generates it. Real parsers handle it by cheating in the lexer, matching names with a stack of strings rather than with the grammar, which is a fine engineering answer and is not a context-free grammar. Length-prefixed records fail the same way: the prefix is a count that must equal the length of what follows, which is a copy of a number into a length.

The practical consequence, and the reason the lemma matters to anyone building constrained decoding or a validator, is that a grammar can enforce the shape of these formats and can never enforce the copy. That has to be checked afterwards, by something that can compare two strings. The pumping lemma is the proof that no cleverness with the grammar will remove the need, and the tall tree is the reason: a grammar's only memory is the path from the root, and a path cannot hold a string it has to repeat.