The Pumping Lemma for Context-Free Languages

Remember the regular pumping lemma — now do it with trees

Back in the regular world you proved that a^n b^n is not regular with the pumping lemma. The idea was the pigeonhole principle in disguise: a DFA has only finitely many states, so on a long enough run it must visit some state twice, and the loop between those two visits can be repeated — pumped — to make new accepted strings. That cornered any language whose strings cannot tolerate such a loop. The previous guide in this rung sharpened a related fact: context-free languages are closed under some operations but not under intersection or complement, with a^n b^n c^n as the headline counterexample. Now we build the tool that actually proves a^n b^n c^n is not context-free.

The trick that worked for regular languages — repeating a state — does not transfer directly, because a pushdown automaton also has an unbounded stack, so 'same state twice' no longer means 'same situation twice'. Instead the context-free pumping lemma reasons about a parse tree, the structure a grammar assigns to a string. A grammar has only finitely many variables (nonterminals). If a string is long, its parse tree must be tall; if the tree is tall, some root-to-leaf path must repeat a variable. That repeated variable is the new pigeonhole, and the chunk of tree between the two copies is what we get to pump.

What the lemma says: five pieces, two of them pump together

Here is the statement. For every context-free language L there is a constant p, the pumping length, such that every string s in L with |s| at least p can be split into five parts, s = u v x y z, satisfying three conditions. First, |v y| is at least 1 — at least one of the two pumpable parts is non-empty, so we are not pumping nothing. Second, |v x y| is at most p — the pumpable middle stays bounded, which is what pins the pieces close together. Third, and the heart of it, for every i = 0, 1, 2, ... the string u v^i x y^i z is also in L. Notice v and y carry the same exponent i: they grow and shrink in lockstep.

Compare this to the regular lemma, which split a string into three parts x y z and pumped a single middle y. The jump from one pumped piece to two is the whole personality of context-free languages. A stack matches things in nested, paired fashion — push on the way in, pop on the way out — so when something repeats, it repeats as a matched pair, like the open and close brackets of one more level of nesting. That is exactly why a^n b^n IS context-free (one v of a's pairs with one y of b's) while a^n b^n c^n is not: two pumped pieces cannot keep three independent counts equal at once.

Why it is true: a tall parse tree must repeat a variable

The proof is a clean pigeonhole argument on parse trees, and it is worth seeing because the structure of the proof is the meaning of the lemma. Put the grammar into a form where every node has at most a fixed number of children (Chomsky normal form does this: each rule is A → B C or A → a, so the parse tree is binary). A binary tree of height h has at most 2^h leaves. So if a string s is long enough — longer than 2^(number of variables) — its parse tree must have height greater than the number of variables, hence some root-to-leaf path is long enough to repeat a variable, say A appears twice on one path.

Picture the two copies of A nested inside each other. The lower A derives some chunk of the string — call it x, the innermost yield. The upper A derives a larger chunk that contains x plus material on its left and right: that left material is v and the right material is y. Everything before the upper A is u, everything after is z. So s = u v x y z. Because both copies are the same variable A, the subtree hanging under the upper A and the subtree under the lower A are interchangeable: A can derive v A y, and A can also derive x. We can splice these together as many times as we like.

Two copies of A on one path:

              S
             /
            A        <- upper A: derives  v x y
          / | \
         v  A  y      <- lower A: derives  x
            |
            x

  A => v A y      (the loop we can repeat)
  A => x          (the base, used to stop)

  i=0:  drop the loop ->  u x z           (pump down)
  i=1:  original       ->  u v x y z
  i=2:  loop twice     ->  u v v x y y z   (pump up)
  general:             ->  u v^i x y^i z   for all i >= 0

This is where the conditions come from, all at once. The two pumped pieces are exactly v and y because they flank the inner subtree — so they always grow as a matched pair. At least one of them is non-empty (|v y| at least 1) provided we chose the grammar so it has no useless epsilon or unit detours, which guarantees the upper A genuinely produces more than the lower one. And |v x y| stays at most p because we picked the lowest repeating variable on the path, keeping its subtree small. The whole lemma is just this one picture, read carefully.

Using it: the adversary game and a^n b^n c^n

To use the lemma you play the same adversary game as in the regular case, now with five pieces. You do not get to choose p, and you do not get to choose the split; the adversary does both. You only choose the string s (cleverly, in terms of p) and the pump exponent i (to force a contradiction). If, no matter how the adversary splits s into u v x y z respecting the two side conditions, some choice of i kicks u v^i x y^i z out of L, then L cannot be context-free. The art is picking s so that every legal split is doomed.

1. Assume for contradiction that L = { a^n b^n c^n : n >= 0 } is context-free, so it has a pumping length p.
2. Choose the witness string s = a^p b^p c^p. Its length is 3p, well above p, so the lemma applies to it.
3. Let the adversary split s = u v x y z with |v y| at least 1 and |v x y| at most p. Because the middle block v x y has length at most p, it is too short to stretch across all three letter regions — it can touch at most two of the three letters a, b, c.
4. Pump up to i = 2, giving u v^2 x y^2 z. The pumping adds copies of v and y, which together lie in at most two of the three regions, so it raises the counts of at most two of the three letters.
5. The third letter's count is untouched, so the three counts can no longer all be equal. The new string is therefore NOT of the form a^n b^n c^n, contradicting that it should be in L. (A split that mixes order, e.g. v containing both a and b, gives an even worse string like ...abab..., still not in L.) Hence L is not context-free.

Sit with why this works and the earlier case a^n b^n does not. With only two letters, two pumped pieces are enough: v can sit among the a's and y among the b's, raising both counts together, so a^n b^n survives every pump and is context-free. With three letters, two pieces can keep at most two regions in sync; the third drifts. The number of independent quantities a language must keep equal, versus the two pumps the lemma allows, is the dividing line. That is the same reason a^n b^n c^n marks the edge of context-free.

When two pumps are not enough: Ogden's lemma

Sometimes the basic pumping lemma is too blunt. Consider a language whose long strings happen to contain a big easy region — say a long run of one harmless letter — that the adversary can park the entire v x y window inside, pumping only that harmless run and never disturbing the part you care about. Then every pump stays in L and the basic lemma fails to expose anything. The string is long, but its length did not force the loop to land where it hurts.

Ogden's lemma is the sharper tool for exactly this situation. It lets you first mark at least p positions of your choosing as 'distinguished', and then guarantees the pumped pieces v and y between them contain at least one marked position — the loop is forced through the spot you marked, not into some convenient padding. The basic pumping lemma is just Ogden's lemma with every position marked. With marking you can also prove certain languages are inherently ambiguous, a job the plain lemma cannot do.