The Chomsky hierarchy chapter introduced a language, 0^n 1^n 2^n, and claimed that no context-free grammar could possibly generate it, since a single stack cannot reliably coordinate three separate matching counts at once. That claim was stated with confidence, but it was never actually proven. This chapter finally closes that gap, introducing the pumping lemma for context-free languages, a direct extension of the ideas covered two chapters ago for regular languages, adapted to work with grammars and their parse trees instead of automata and their states.
If the regular pumping lemma felt intimidating at first, this version will likely feel doubly so on paper, since it involves splitting a string into five pieces instead of three, with two separate segments being pumped simultaneously rather than one. The underlying intuition, however, is built on exactly the same foundation as before: a counting argument, this time applied to the height of a parse tree rather than the states visited by a DFA.
In this tutorial, you will learn why the context-free pumping lemma needs five pieces instead of three, its precise formal statement, and a complete worked proof demonstrating that 0^n 1^n 2^n is not context-free, finally justifying the claim made back in the Chomsky hierarchy chapter.
Recall that the regular pumping lemma relies on the pigeonhole principle applied to the states a DFA visits while processing a long string. A context-free grammar has no states in this sense, so the argument needs to be rebuilt around a different structure: the parse tree.
Every context-free grammar can be converted into an equivalent grammar in a restricted form, called Chomsky normal form, where every production rule produces either exactly two non-terminals or exactly one terminal. In such a grammar, the parse tree for any derived string is guaranteed to be a binary tree. If the grammar has, say, k non-terminals, and the parse tree for a particular string is tall enough, taller than k levels along some path from the root, then the pigeonhole principle guarantees that some non-terminal must repeat along that path, appearing at two different heights in the same branch of the tree.
Once a non-terminal repeats along a single path in the parse tree, the portion of the derivation between the two occurrences represents a self-contained "loop" in the grammar, very similar in spirit to the looping segment found in the regular pumping lemma. Because the tree is binary, and because this repeated non-terminal sits above two other subtrees, this loop actually produces two separate pumpable pieces at once, one on the left side of the middle portion, and one on the right side, which is exactly why the string ends up split into five parts instead of three.
If L is a context-free language, then there exists a number p, called the pumping length, such that every string w in L with length at least p can be split into five parts, w = uvwxy, satisfying all of the following conditions:
| Condition | Meaning |
|---|---|
| |vx| > 0 | At least one of v or x must be non-empty; there must be something to pump. |
| |vwx| ≤ p | The middle three pieces together, v, w, and x, must fit within a bounded portion of the string, corresponding to the bounded height of the repeated section of the parse tree. |
| uv^i w x^i y ∈ L for every i ≥ 0 | Pumping v and x together, the same number of times simultaneously, must always produce another string that still belongs to L. |
Notice the crucial detail in the third condition: v and x are always pumped together, using the same exponent i, never independently. This reflects the fact that both segments come from the two subtrees hanging beneath the single repeated non-terminal in the parse tree, so both must be repeated the same number of times whenever that non-terminal's derivation is repeated.
The overall proof strategy remains exactly the same proof-by-contradiction technique used for regular languages. Assume the suspicious language L is context-free. By the lemma, some pumping length p must exist. Choose a specific string in L, at least p symbols long, cleverly designed to break under any possible valid split into u, v, w, x, and y. Show that no matter how the split is chosen, respecting the length and non-emptiness restrictions, pumping v and x together always produces a string outside L. This contradiction proves L cannot be context-free.
The added complexity compared to the regular pumping lemma comes entirely from having to consider two pumpable pieces, v and x, rather than just one, and reasoning carefully about where those two pieces could possibly fall within the chosen string.
Consider the language L = { 0^n 1^n 2^n | n ≥ 1 }, consisting of some number of 0s, followed by exactly the same number of 1s, followed by exactly the same number of 2s. This is precisely the language mentioned back in the Chomsky hierarchy chapter as an example of a language beyond the reach of context-free grammars.
Assume L = { 0^n 1^n 2^n | n ≥ 1 } is context-free.
By the pumping lemma for context-free languages, some pumping length p exists
satisfying all three conditions for every string in L of length at least p.
The string must belong to L and have length at least p. A convenient choice is:
w = 0^p 1^p 2^p
This string clearly belongs to L, consisting of exactly p zeros, followed by exactly p ones, followed by exactly p twos, with total length 3p, certainly at least p.
By the second condition, |vwx| ≤ p, meaning the combined middle segment vwx must fit within a window of at most p consecutive symbols somewhere in w. Since w consists of three separate blocks of p symbols each, all identical within their own block, a window of at most p symbols can overlap at most two of these three blocks; it can never touch all three blocks 0, 1, and 2 at the same time, since doing so would require spanning more than p symbols in total.
This observation is the heart of the entire proof: no matter where vwx falls, at least one of the three symbols, 0, 1, or 2, is guaranteed to be completely absent from the combined segment vwx.
| Case | What Happens When Pumping |
|---|---|
| vwx falls only within the 0s, or only within the 2s | Pumping increases the count of only that one symbol, breaking the equality between all three counts. |
| vwx overlaps the boundary between 0s and 1s, containing only 0s and 1s | Pumping increases the combined count of 0s and 1s while leaving the count of 2s unchanged, breaking equality. |
| vwx overlaps the boundary between 1s and 2s, containing only 1s and 2s | Pumping increases the combined count of 1s and 2s while leaving the count of 0s unchanged, breaking equality. |
In every single case, since vwx can never contain all three symbols simultaneously, pumping v and x up, using i = 2, always changes the count of at least one symbol without changing the counts of all three symbols equally.
Consider pumping with i = 2, producing uv^2wx^2y. Since |vx| > 0, at least one of v or x is non-empty, so at least one symbol's count strictly increases. Since vwx cannot span all three blocks at once, at least one symbol's count remains completely unchanged. Therefore, uv^2wx^2y cannot have equal counts of 0s, 1s, and 2s, meaning uv^2wx^2y is not of the form 0^n 1^n 2^n for any single n.
Contradiction reached: uv^2wx^2y is required to be in L by the pumping lemma,
but it has been shown that uv^2wx^2y is not in L for any possible valid split.
Therefore, the original assumption that L is context-free must be false.
L = { 0^n 1^n 2^n | n ≥ 1 } is not a context-free language.
This completes the proof that was only asserted, not demonstrated, back in the Chomsky hierarchy chapter. The core reason 0^n 1^n 2^n escapes context-free grammars is exactly what the case analysis above reveals: a bounded window of symbols, no matter where it is placed, simply cannot straddle all three separated blocks at once, so pumping is always guaranteed to break at least one of the three required equal counts.
This proof directly reinforces the structural explanation given in the previous chapter: a pushdown automaton's single stack is well-suited to comparing two quantities against each other, as seen with 0^n 1^n, but it has no natural way to keep three separate quantities synchronized simultaneously. The pumping lemma formalizes this intuition into an airtight mathematical proof, showing that no context-free grammar, no matter how cleverly designed, can ever generate 0^n 1^n 2^n.
Languages like this one, which require more coordination than a single stack can offer, sit at the context-sensitive level of the Chomsky hierarchy, requiring a linear bounded automaton rather than a pushdown automaton to recognize them correctly.
| Mistake | Correct Understanding |
|---|---|
| Assuming v and x can be pumped independently, using different exponents. | The pumping lemma always pumps v and x together, using the exact same exponent i, since both come from the same repeated non-terminal's derivation. |
| Forgetting that |vwx| ≤ p restricts the middle segment to a bounded window. | This restriction is exactly what guarantees the segment cannot span all three separated blocks in the 0^n 1^n 2^n proof. |
| Believing |v| > 0 and |x| > 0 must both hold individually. | The actual condition only requires |vx| > 0, meaning at least one of v or x must be non-empty, not necessarily both. |
| Trying to apply the regular pumping lemma directly to a context-free language proof. | The context-free version requires its own five-piece split and simultaneous pumping of two segments, not the three-piece structure used for regular languages. |
The pumping lemma for context-free languages extends the same core counting argument used for regular languages, this time built around the height of a binary parse tree rather than the states of a DFA, resulting in a string split into five parts with two segments pumped simultaneously. Through a complete worked proof, this chapter finally demonstrated that 0^n 1^n 2^n, mentioned back in the Chomsky hierarchy chapter, genuinely lies beyond the reach of any context-free grammar or pushdown automaton.
In this tutorial, you learned why five pieces are needed instead of three, the precise formal statement of the context-free pumping lemma, and a complete worked proof using careful case analysis to show 0^n 1^n 2^n is not context-free. With this technique in hand, you are ready to move on to Turing machines, the most powerful computational model studied in this course, capable of recognizing languages far beyond both regular and context-free languages.