Pumping lemma for context-free languages
Pumping lemma for context-free languages: a necessary property used to prove some languages are not context-free, derived from parse trees of grammars in Chomsky normal form.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Engineers use the pumping lemma for context-free languages to prove that certain languages cannot be described by context-free grammars or pushdown automata. This helps when choosing correct models (e.g., deciding whether a compiler feature can be parsed by a PDA or requires stronger machinery like a Turing machine or context-sensitive grammar).
Key ideas
Start with simple definitions (plain English):
- Alphabet: a finite set of symbols. Example: Σ = {a, b, c}.
- String: a finite sequence of symbols from an alphabet. The length of a string s is written |s| and is unitless.
- Language: a set of strings over an alphabet.
- Context-free grammar (CFG): a 4-tuple G = (V, Σ, R, S) where V is a finite set of nonterminals (variables), Σ is the alphabet of terminals, R is a finite set of production rules of the form A → α where A ∈ V and α ∈ (V ∪ Σ)*, and S ∈ V is the start symbol. A language generated by a CFG is a context-free language (CFL).
- Parse tree: a rooted ordered tree representing a derivation of a string from the start symbol using grammar rules (leftmost or rightmost derivations yield the same parse tree). The leaves, read left-to-right, form the yield (the derived terminal string).
- Chomsky normal form (CNF): a CFG is in CNF if every production is either A → BC (two nonterminals) or A → a (single terminal), except possibly S → ε. Every CFG (except those generating ε specially) can be converted to an equivalent CFG in CNF. If ε ∈ L, allow S → ε with S not appearing on any rule’s right-hand side.
Pumping lemma (statement, exact university style):
Let L be an infinite context-free language. Then there exists an integer p ≥ 1 (called a pumping length) such that for every string s in L with |s| ≥ p, we can write s = u v w x y (strings u,v,w,x,y ∈ Σ*) satisfying
- |v w x| ≤ p,
- |v x| ≥ 1,
- For all integers i ≥ 0, the string u v^i w x^i y ∈ L.
This is a necessary condition: every infinite CFL satisfies it; a language that does not satisfy it cannot be context-free. The lemma does not give a sufficient condition — a language that satisfies the lemma may still be non-context-free.
Intuition and where p comes from (proof idea universities expect):
- Convert a CFG for L into CNF. Let n = |V| be the number of nonterminals.
- A parse tree for a string s produced by a CNF grammar is a binary tree (every internal node has two children when it uses A → BC). A binary tree of height h (number of nodes on the longest root-to-leaf path) can have at most 2^{h-1} leaves (terminals in the yield).
- If |s| ≥ 2^{n}, then any parse tree for s must have height ≥ n+1. A path from the root to a leaf then has length ≥ n+1, but there are only n nonterminals, so by the pigeonhole principle some nonterminal A appears at least twice on that path. Use the repeated A to define the decomposition u v w x y where the middle part vwx corresponds to the yield of the subtree between the two occurrences of A.
- Because the repeated nonterminal can be replaced any number of times in the derivation, pumping (repeating the subderivation) yields u v^i w x^i y ∈ L for all i ≥ 0. The bounds |vwx| ≤ p and |vx| ≥ 1 come from choosing p = 2^{n} and from the fact that at least one symbol is generated between the repeated nodes.
Important remarks (common exam clarifications):
- The lemma requires L to be infinite. For finite languages pumping lemma is trivial or inapplicable. When using the lemma you must first justify (or, in a contradiction proof, assume) that L is infinite before invoking the lemma, and then choose s with |s| ≥ p.
- Quantifiers order matters: ∃p such that ∀s with |s| ≥ p ∃ a decomposition with properties that ∀i, uv^i w x^i y ∈ L. Many students swap ∃ and ∀ incorrectly — that makes the argument invalid.
- The pumping length p is dependent on the grammar (hence on L) but need not be computed exactly in exam answers; you may assume a p exists and pick s with |s| ≥ p.
- A correct pumping proof requires a case analysis that covers every possible decomposition (every allowed position of v and x inside s), not just one convenient decomposition.
Diagram to draw in an exam when deriving the lemma or explaining it:
- Draw a binary parse tree (root labelled S). Mark a single root-to-leaf path of length n+1 showing repeated nonterminal A twice (label them A_1 and A_2). Show the subtree at the upper A producing v w x and the lower A producing w; the whole tree yields u v w x y. Label the segments of the yield under the tree leaves left-to-right as u, v, w, x, y. Annotate that pumping the lower A repeats the v and x pieces.
Formulas
s = u v w x y — s is split into five parts; unitless strings.
|v w x| ≤ p — the middle three parts together have length at most p; p is the pumping length, unitless.
|v x| ≥ 1 — at least one of v or x is non-empty; unitless.
∀ i ≥ 0, u v^i w x^i y ∈ L — every pumped string is in the language; i is integer, unitless.
p = 2^{|V|} (one valid choice in the CNF-based proof) — p chosen from the number |V| of nonterminals; unitless. Verify this exact bound if your professor expects a specific numeric bound.
Worked examples
Example 1 — Classical exam question (prove non-CFL):
Question: Prove that L = { a^n b^n c^n | n ≥ 0 } is not a context-free language.
Model answer (step-by-step):
- Assume, for contradiction, that L is context-free and infinite. Then the pumping lemma for CFLs applies; let p be the pumping length from the lemma.
- Choose the string s = a^p b^p c^p ∈ L (|s| = 3p ≥ p).
- By the lemma, s = u v w x y with |v w x| ≤ p and |v x| ≥ 1, and for all i ≥ 0, u v^i w x^i y ∈ L.
- Because |v w x| ≤ p, the substring v w x lies entirely inside a block of consecutive symbols of s that spans at most two of the letter-blocks a^p, b^p, c^p. That is, v and x cannot simultaneously contain symbols from all three blocks a, b and c. Consider cases:
- Case A: v w x lies entirely within the a^p block. Then v and x contain only a's. Pumping with i = 0 removes some a's but leaves the number of b's and c's at p. The pumped string has fewer a's than b's or c's, so it cannot be in L (which requires equal counts). Contradiction.
- Case B: v w x lies entirely within the b^p block. Similar: pumping changes number of b's only, breaking equality.
- Case C: v w x lies entirely within the c^p block. Similar contradiction.
- Case D: v w x spans the boundary between a^p and b^p (or b^p and c^p). Then pumping changes counts of two kinds of letters but not the third; pick i = 0 or i = 2 to make counts unequal (e.g., remove some a's and b's but c's remain p). Contradiction.
- Every possible case leads to a contradiction. Therefore L is not context-free. QED.
Example 2 — Showing a language is context-free and why pumping lemma is not useful to show otherwise:
Question: Show that L' = { a^m b^n c^n | m,n ≥ 0 } is context-free.
Model answer:
- Construct a CFG G with start symbol S and rules:
- S → A B
- A → a A | ε
- B → b B c | ε
- A generates a^m and B generates b^n c^n. So L(G) = L'. Thus L' is a CFL.
- Note: Because L' is CFL, pumping lemma must hold for some p. Attempts to use pumping lemma to derive a contradiction will fail — the lemma is only useful to prove non-CFL, not to disprove CFLness.
Common mistakes
- Assuming the decomposition is fixed ahead of time — the lemma says ∃ decomposition for each s, so you must handle all possible decompositions that satisfy the lemma's constraints.
- Forgetting
|v x| ≥ 1(i.e., allowing both v and x to be empty) — this invalidates the pumping effect. - Not doing a complete case analysis — you must cover every possible location of v and x inside s according to |vwx| ≤ p.
- Using pumping lemma to try to prove a language is context-free. The lemma is only a necessary condition; satisfying it does not guarantee CFL.
For your exam
Types of questions you will see:
- State and prove (sketch) the pumping lemma for CFLs (expect CNF-based parse-tree proof sketch).
- Use the pumping lemma to show a language is not a CFL (typical long question). Provide full case analysis and clear explanation of why each case contradicts the lemma.
- Short notes: difference between pumping lemma for regular languages and for CFLs, and mention of stronger results like Ogden's lemma. Difference in form: for regular languages s = x y z with |y| ≥ 1 and |x y| ≤ p and pumping affects y; for CFLs s = u v w x y with |v x| ≥ 1 and |v w x| ≤ p and pumping affects both v and x simultaneously.
What a full-marks answer includes:
- Exact statement of the pumping lemma with correct quantifier order and constraints
|vwx| ≤ p,|vx| ≥ 1. - A clear start: assume L is CFL and infinite, invoke lemma and specify p.
- A valid choice of witness string s with |s| ≥ p.
- Exhaustive case analysis covering all possible decompositions allowed by the lemma.
- A concluding contradiction showing the pumped string is not in L for some i, and therefore L is not CFL.
- If asked for the lemma proof: CNF conversion, parse-tree picture and pigeonhole argument with repeated nonterminal.
Quick check
- State the pumping lemma for context-free languages in one sentence.
- Why must you ensure the chosen string s satisfies |s| ≥ p when applying the lemma?
- Give one language that is known to be not context-free and one that is context-free.
Answers: 1) See lemma statement above: ∃p such that ∀s ∈ L with |s| ≥ p ∃ decomposition s=uvwxy with |vwx| ≤ p, |vx| ≥1 and ∀i ≥0 uv^i w x^i y ∈ L. 2) Because the lemma only guarantees the decomposition and pumping property for strings of length at least p. 3) Not CFL: {a^n b^n c^n | n ≥0}. CFL: {a^m b^n c^n | m,n ≥0}.
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?