Pushdown automata and context-free grammars are more powerful than finite automata, but they still have limits. A PDA has only one stack, so it can match an against bn, but it cannot also check cn. How do we prove that no PDA and no grammar at all can handle anbncn?
The tool is the pumping lemma for context-free languages, the big brother of the lemma in Pumping Lemma for Regular Languages. The regular version pumps one piece of a string. The context-free version pumps two pieces at the same time, because a parse tree can repeat a variable and grow on both sides of it.
Pumping lemma for CFLs: if L is a context-free language, then there is a constant p ≥ 1 (the pumping length) such that every string z ∈ L with |z| ≥ p can be written as z = uvwxy where (1) |vwx| ≤ p, (2) |vx| ≥ 1, and (3) uviwxiy ∈ L for every i ≥ 0.
In this chapter we will understand where the lemma comes from, prove it, and then use it to show that several important languages are not context-free. All proofs were also double-checked by a program that tried every possible decomposition uvwxy for small pumping lengths.
Intuition: Repeated Variables in a Parse Tree
Take a grammar and a very long string. Its parse tree must be tall: a tree whose nodes have only a few children cannot have many leaves unless it has long paths. On a long enough path from the root to a leaf, some variable, call it A, must appear twice (there are only finitely many variables).
S
/ | \
/ A \ upper A derives v w x
/ /|\ \ lower A derives w
/ / A \ \
/ / | \ \
u v w x y
z = u v w x y, A ⇒* vAx, A ⇒* w
The upper A derives vAx (the lower A with some material v on its left and x on its right). The lower A derives w. Now we can play with the tree:
Pump down (i = 0): replace the subtree of the upper A by the subtree of the lower A. The tree now yields uwy.
Pump up (i = 2): replace the subtree of the lower A by a copy of the upper A's subtree. The tree now yields uvvwxxy. Repeating gives uviwxiy for any i.
Every one of these trees is a valid parse tree of the same grammar, so all these strings are in L. The two pieces v and x grow together, the same number of times. That linkage is what lets CFLs count two things against each other (like anbn), and also what limits them to that.
Proof of the Lemma
Let G be a grammar in Chomsky Normal Form for L − {ε}, with k variables. Set p = 2k.
Fact (size of CNF parse trees). Measure the height of a parse tree as the number of edges on its longest root-to-leaf path. In CNF, if the height is h, the yield has at most 2h−1 symbols. Reason: the last edge of every path is a production A → a (one child), and every edge above it comes from A → BC (two children), so the tree is a binary tree of height h − 1 with one terminal hanging below each bottom variable.
Step 1: a long path exists. Let z ∈ L with |z| ≥ p = 2k. Since 2k > 2k−1, the fact above says the parse tree of z has height at least k + 1. Take a longest path. It has at least k + 1 edges, hence at least k + 2 nodes; all of them except the leaf are variables, so it has at least k + 1 variable nodes.
Step 2: a repetition near the bottom. Look only at the lowest k + 1 variable nodes on this path. There are only k different variables, so by the pigeonhole principle two of these nodes carry the same variable A. Call the higher one A1 and the lower one A2. Let vwx be the yield of A1's subtree and w the yield of A2's subtree; then z = uvwxy.
Step 3: |vwx| ≤ p. The path from A1 down to the leaf has at most k + 1 edges (A1 is among the bottom k + 1 variables). Since we chose a longest path of the whole tree, no path inside A1's subtree can be longer than that; otherwise we could extend it upward into a longer path of the whole tree. So the subtree has height ≤ k + 1 and yield length ≤ 2k = p.
Step 4: |vx| ≥ 1. A1 has two children (A1 → BC). A2 lies inside one of them; the other child derives a non-empty string (CNF has no ε-productions), and that string is part of v or of x.
Step 5: pumping. As explained above, A ⇒* vAx and A ⇒* w, so S ⇒* uAy ⇒* uviAxiy ⇒* uviwxiy for every i ≥ 0. ∎
How to Use the Lemma: The Adversary Game
Like the regular version, the lemma gives a property every CFL has. To show L is not context-free, assume it is and reach a contradiction. It helps to think of a game against an opponent:
Step | Who chooses | What |
|---|---|---|
1 | Opponent | The pumping length p (you must handle every p) |
2 | You | A string z ∈ L with |z| ≥ p (choose it cleverly, in terms of p) |
3 | Opponent | A split z = uvwxy with |vwx| ≤ p and |vx| ≥ 1 (you must handle every split) |
4 | You | A value i ≥ 0 such that uviwxiy ∉ L |
If you can always win, L is not context-free. The window condition |vwx| ≤ p is your most important weapon: the pumped region is short, so it cannot touch parts of the string that are far apart.
Example 1: L = { anbncn : n ≥ 0 } Is Not Context-Free
Proof. Suppose L is context-free with pumping length p. Choose
z = a^p b^p c^p (in L, length 3p ≥ p)
Let z = uvwxy be any split with |vwx| ≤ p and |vx| ≥ 1.
Key observation: vwx cannot contain both an a and a c. Between the last a and the first c there are p b's, so any substring containing both has length at least p + 2 > p.
So vx contains symbols from at most two of the three letters, and at least one symbol in total. Pump down (i = 0): the string uwy is obtained from z by deleting the symbols of v and x.
If vx contains no c: uwy still has p c's, but it has fewer than p a's or fewer than p b's (we deleted at least one a or b).
If vx contains a c: then it contains no a, so uwy still has p a's but fewer than p c's.
Either way the three counts in uwy are not all equal, so uwy ∉ L. This contradicts the lemma, so L is not context-free. ∎
(Pumping up with i = 2 also works: if v or x contains two different letters, uv2wx2y has letters out of order; otherwise at most two counts grow. Many textbooks use that version.)
Example with p = 4: z = aaaa bbbb cccc
Opponent's split: u = aaa, v = ab, w = b, x = b, y = bcccc (|vwx| = 4)
i = 0: u w y = aaa b bcccc = aaabbcccc counts 3, 2, 4 → not in L
i = 2: u vv w xx y = aaa abab b bb bcccc = aaaababbbbbcccc out of order → not in L
Example 2: L = { ww : w ∈ {a, b}* } Is Not Context-Free
This is a classic surprise: wwR (a string followed by its reverse) is context-free, but ww (a string followed by a copy of itself) is not. A stack gives back symbols in reverse order, which suits wwR but not ww.
Choosing z carefully. A tempting choice is z = apb apb. It does not work: the opponent picks u = ap−1, v = a, w = b, x = a, y = ap−1b, and then uviwxiy = ap−1+ib ap−1+ib, which is in L for every i. Choosing z badly is the most common way to "fail" a pumping proof.
Proof. Suppose L is context-free with pumping length p. Choose
z = a^p b^p a^p b^p (= ww with w = a^p b^p, length 4p)
Let z = uvwxy with |vwx| ≤ p, |vx| = m ≥ 1, and pump down: s = uwy has length 4p − m. If m is odd, |s| is odd and s ∉ L. So assume m is even, 2 ≤ m ≤ p. Then s has length 4p − m, and each half has length 2p − m/2. Since |vwx| ≤ p, there are three cases:
vwx lies inside the first 2p symbols. The last 2p symbols of z, apbp, are untouched, so s ends with b. The first half of s consists of the first 2p − m symbols left over from the first apbp, followed by m/2 ≥ 1 a's from the second block. So the first half ends with a, but the second half ends with b. The halves differ: s ∉ L.
vwx lies inside the last 2p symbols. Now the first 2p symbols apbp are untouched. The second half of s starts at position 2p − m/2 + 1, which lies inside the first bp block (since 1 ≤ m/2 ≤ p/2), so the second half starts with b, while the first half starts with a. s ∉ L.
vwx straddles the middle. Then vwx lies inside the middle bpap, so s = apbjalbp with j + l = 2p − m, so j < p or l < p. If s = tt, then t starts with a and ends with b (because s does), so tt has twice as many blocks of a's as t, and s has at most two such blocks. Hence t = aαbβ and s = aαbβaαbβ, which forces α = p = l and β = j = p. That contradicts j < p or l < p. So s ∉ L.
In every case uwy ∉ L, a contradiction. So { ww } is not context-free. ∎
Example 3: L = { an² : n ≥ 0 } Is Not Context-Free
Over a one-letter alphabet, u, v, w, x, y are all blocks of a's, so only lengths matter.
Proof. Choose z = ap². For any split, let m = |vx|, with 1 ≤ m ≤ |vwx| ≤ p. Pump up (i = 2): the length becomes p2 + m, and
p² < p² + m ≤ p² + p < p² + 2p + 1 = (p + 1)²
So p2 + m lies strictly between two consecutive perfect squares and is not a square. uv2wx2y ∉ L. ∎
The same style of proof shows that { a2n } and { aq : q is prime } are not context-free. In fact, a stronger fact holds: every context-free language over a one-letter alphabet is regular (a consequence of Parikh's theorem). So a unary language that is not regular is automatically not context-free either.
The Lemma Is Only a Necessary Condition
Be careful with the direction of the logic:
Statement | True? |
|---|---|
L is a CFL ⟹ L satisfies the pumping property | Yes (the lemma) |
L fails the pumping property ⟹ L is not a CFL | Yes (contrapositive; this is how we use it) |
L satisfies the pumping property ⟹ L is a CFL | No |
Some non-context-free languages can be pumped. A standard example is L = { aibjckdl : i = 0 or j = k = l }: every long string can be pumped (if i ≥ 1, pump a single a; strings with i = 0 have no restriction on b, c, d, so pump inside them), yet L is not context-free. Proving that needs a stronger tool, Ogden's lemma, which lets you "mark" some positions of z and forces v or x to contain marked positions. For exams, remember that Ogden's lemma exists and is a generalisation of the pumping lemma.
Another powerful technique is to combine the lemma with closure properties: CFLs are closed under intersection with a regular language. For example, if L = { w ∈ {a, b, c}* : #a = #b = #c } were context-free, then L ∩ a*b*c* = { anbncn } would be too, contradicting Example 1. (The reason the intersection stays context-free is simple: run a PDA for L and a DFA for the regular language side by side, keeping the DFA state inside the PDA state. The full proof is in the next chapter, Closure & Decision Properties of CFLs.)
Regular vs Context-Free Pumping Lemma
Aspect | Regular languages | Context-free languages |
|---|---|---|
Decomposition | w = xyz (3 parts) | z = uvwxy (5 parts) |
Pumped parts | One: y | Two together: v and x |
Length condition | |xy| ≤ p (pumped part near the start) | |vwx| ≤ p (pumped window anywhere) |
Non-empty condition | |y| ≥ 1 | |vx| ≥ 1 (one of v, x may be empty) |
Source | A repeated DFA state on a path | A repeated variable on a parse-tree path |
Typical p | Number of DFA states | 2k for a CNF grammar with k variables |
Classic victim | anbn | anbncn, ww |
Why does anbn survive the CFL lemma? With z = apbp, the opponent picks v = a and x = b right at the boundary: uviwxiy = ap−1+ibp−1+i stays in L. Two linked pumps can keep two counts equal, but not three.
Quick Reference: CFL or Not?
Language | Context-free? | Why |
|---|---|---|
{ anbn }, { anbmcn }, { anbncm } | Yes | Only one pair of counts compared (nested) |
{ anbmcmdn } | Yes | Two comparisons, properly nested |
{ anbmcndm } | No | Two comparisons that cross |
{ anbncn } | No | Three-way equality (Example 1) |
{ aibjck : i = j or j = k } | Yes | Union of two CFLs (inherently ambiguous) |
{ wwR } | Yes | Stack reverses |
{ ww } | No | Example 2 |
Complement of { ww } over {a, b} | Yes | A known (non-obvious) result: guess a position where the halves differ |
{ an² }, { a2n }, { aq : q prime } | No | Unary and not regular |
{ ambn : m ≠ n } | Yes | Union of m > n and m < n |
A useful rule of thumb: CFLs can compare counts that are nested like brackets (the first block with the last, the second with the second-last), but not counts that cross or three-way equalities. This is a heuristic for guessing; the pumping lemma (or closure properties) is what proves it.
Common Mistakes
Choosing the split yourself. You choose z and i; the opponent chooses p and u, v, w, x, y. Your argument must work for every legal split.
Forgetting that v or x may be empty. Only |vx| ≥ 1 is guaranteed.
Ignoring |vwx| ≤ p. Without it, the case analysis explodes and many proofs become impossible. It is what stops vwx from touching both the a's and the c's.
Picking a z that can be pumped, such as apbapb for ww. Pick z so that every short window is "trapped".
Concluding that a language is context-free because it can be pumped. The lemma never proves a language is context-free; give a grammar or a PDA for that.
Choosing a fixed number instead of p, e.g. z = a5b5c5. The string must depend on p so that |z| ≥ p for every possible p.
Practice and GATE-Style Questions
Q1. Prove that L = { anbmcndm : n, m ≥ 0 } is not context-free.
Take z = apbpcpdp. Since |vwx| ≤ p, vwx lies within at most two adjacent blocks: (a, b), (b, c) or (c, d). Pump down to uwy, which is still of the form a*b*c*d*. If vx contains an a, then vx contains no c, so #a < p = #c. If vx contains a c but no a, then #c < p = #a. Otherwise vx contains only b's and/or d's but not both (b and d are not adjacent), so #b ≠ #d. In every case uwy ∉ L. ∎ (A program confirmed that i = 0 defeats every split for p = 1 to 6.)
Q2. Can the pumping lemma prove that { anbn } is not context-free? Why or why not?
No, because it is context-free (S → aSb | ε). For z = apbp, the opponent can choose u = ap−1, v = a, w = ε, x = b, y = bp−1. Then uviwxiy = ap−1+ibp−1+i ∈ L for every i, so no contradiction can ever be reached. (The same happens for any other choice of z in L.)
Q3. Which of these are context-free? (i) { anb2ncn } (ii) { anbm : m = 2n + 1 } (iii) { aibjck : i < j < k } (iv) { aibjck : i + j = k }
(ii) and (iv) are context-free: (ii) via S → aSbb | b; (iv) via S → aSc | T, T → bTc | ε (each a and each b is matched with a c, nested). (i) and (iii) are not: both need a three-way comparison. For (iii), take z = apbp+1cp+2; vx cannot contain both a and c. Case 1, vx has no c: pump up (i = 2). If vx contains a b, then #b ≥ p + 2 = #c; if it contains only a's, then #a ≥ p + 1 = #b. Case 2, vx has c's but no b: pump down (i = 0), giving #c ≤ p + 1 = #b. Case 3, vx has both b's and c's: pump down, giving #b ≤ p = #a. (Pumping up in case 3 would fail: v = b, x = c gives apbp+2cp+3, which is in L. Choosing i per case matters.) A program confirmed this case analysis for p = 1 to 6.
Q4. A grammar in CNF has 5 variables. What pumping length does the proof give? Must every string of that length or more have a repeated variable on some path?
p = 25 = 32. Yes: a CNF parse tree of a string of length ≥ 32 has height at least 6, so its longest path has at least 6 variable nodes, and with only 5 variables one must repeat.
Q5. Interview: why does the CFL pumping lemma pump two substrings instead of one?
The repetition happens at a variable A inside a parse tree, and A ⇒* vAx puts new material on both sides of the inner A. Repeating that derivation adds the same number of copies of v on the left and x on the right. This is the grammar-level picture of a PDA pushing symbols (v) and later popping them (x).
Summary
Every CFL L has a pumping length p: every z ∈ L with |z| ≥ p splits as uvwxy with |vwx| ≤ p, |vx| ≥ 1 and uviwxiy ∈ L for all i ≥ 0.
Proof: in a CNF grammar with k variables and p = 2k, a long string forces a tall parse tree, whose longest path repeats a variable A among its bottom k + 1 variables; A ⇒* vAx and A ⇒* w.
Use it by contradiction: you pick z (in terms of p) and i; the opponent picks p and the split.
Standard non-CFLs: anbncn, ww, anbmcndm, an², aprime.
The lemma is necessary but not sufficient; Ogden's lemma and closure properties are stronger tools.
A long enough derivation must reuse a variable, and a reused variable can be reused again: v and x always pump together. Pick z so that no short window vwx can keep the language's conditions balanced.