Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

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

  1. |v w x| ≤ p,
  2. |v x| ≥ 1,
  3. 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):

  1. 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.
  2. Choose the string s = a^p b^p c^p ∈ L (|s| = 3p ≥ p).
  3. 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.
  4. 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.
  5. 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:

  1. Construct a CFG G with start symbol S and rules:
    • S → A B
    • A → a A | ε
    • B → b B c | ε
  2. A generates a^m and B generates b^n c^n. So L(G) = L'. Thus L' is a CFL.
  3. 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

  1. State the pumping lemma for context-free languages in one sentence.
  2. Why must you ensure the chosen string s satisfies |s| ≥ p when applying the lemma?
  3. 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?