Context-free languages are far more expressive than regular ones, but they have limits too. To prove that a language is not context-free there is a version of the pumping lemma adapted to grammars. The idea resembles the one for finite automata, but the repetition concerns a variable in a parse tree, and there are now two parts to pump, which grow together.
The intuition: a variable repeats along a path
Take a grammar in Chomsky normal form, where every rule is A → BC or A → a. Parse trees are binary. A binary tree of height h has at most 2ʰ leaves, so a very long string requires a tall tree.
If the grammar has k variables and the string is long enough, there is a path from the root to a leaf with more than k variables. By the pigeonhole principle, some variable R appears twice on that path. The subtree rooted at the upper R contains the one rooted at the lower R.
This situation allows two operations:
- replace the lower subtree with a copy of the upper one, giving a longer string;
- replace the upper subtree with the lower one, giving a shorter string.
What is added or removed is two pieces, one to the left and one to the right of the central part.
The statement
If L is context-free, there is p ≥ 1 such that every string s ∈ L with |s| ≥ p can be written as s = uvxyz with:
- |vy| ≥ 1 (at least one of the two pumped pieces is non-empty);
- |vxy| ≤ p (the pumped window is short);
- uvⁱxyⁱz ∈ L for every i ≥ 0.
As in the regular case, proving non-membership is a game against an adversary: they choose p and the decomposition, we choose the string and the exponent i.
Example 1: aⁿbⁿcⁿ
Let L = {aⁿbⁿcⁿ : n ≥ 0}. Given p, choose s = aᵖbᵖcᵖ.
The condition |vxy| ≤ p is decisive: a window of length at most p cannot touch both the a's and the c's, because p b's lie between them. So v and y contain at most two of the three kinds of letter.
Pumping with i = 2 increases the count of at least one kind of letter, but not of all three. The three counts are no longer equal, and the string leaves L. Moreover, if v or y contains mixed letters, such as "ab", pumping produces letters out of order. Either way L is not context-free.
Example 2: the repeated string
Let L = {ww : w ∈ {a, b}*}. It is an instructive case, because the very similar language {wwᴿ} of even palindromes is context-free.
Choose s = aᵖbᵖaᵖbᵖ. Consider where the window vxy, of length at most p, can lie:
- if it lies entirely in the first half, pumping with i = 0 shortens only the first half; the resulting string can no longer be split into two identical copies;
- if it lies entirely in the second half, the argument is symmetric;
- if it straddles the middle, it contains only b's from the first half and a's from the second; with i = 0 we get a string of the form aᵖbʲaᵏbᵖ with j or k less than p, which is not of the form ww.
In every case we leave L.
Closure properties
It is often quicker to use closure properties. Context-free languages are closed under:
- union: S → S₁ | S₂;
- concatenation: S → S₁S₂;
- star: S → SS₁ | ε;
- intersection with a regular language: run a pushdown automaton and a finite automaton, which uses no stack, in parallel.
They are not closed under intersection and complement. The classic counterexample: {aⁿbⁿcᵐ} and {aᵐbⁿcⁿ} are both context-free, but their intersection is aⁿbⁿcⁿ, which is not. Since intersection can be expressed with union and complement, closure under complement would imply closure under intersection.
A proof by closure
Let L be the language of strings over {a, b, c} with equally many a's, b's and c's, in any order. If L were context-free, so would be L ∩ a*b*c*, because a*b*c* is regular. But that intersection is exactly aⁿbⁿcⁿ. Hence L is not context-free. No decomposition to analyse.
Common mistakes
- Forgetting that v and y can lie in different regions of the string: every placement of the window must be considered.
- Not exploiting |vxy| ≤ p, which is almost always the condition that makes the proof work.
- Thinking that passing the pumping lemma proves a language context-free: it is a necessary condition, not a sufficient one. For hard cases stronger tools exist, such as Ogden's lemma.
In short
- In a tall parse tree a variable repeats, which allows two parts to be pumped together.
- The lemma guarantees s = uvxyz with |vy| ≥ 1, |vxy| ≤ p and uvⁱxyⁱz in the language for every i.
- aⁿbⁿcⁿ and {ww} are not context-free.
- Context-free languages are closed under union, concatenation, star and intersection with regular languages.
- They are not closed under intersection and complement, which yields quick proofs.
