Pumping Lemma for CFL

Theory of Computation & Computer Graphics — Introduction to Context Free Language, NEC licence examination syllabus (Nepal Engineering Council).

Pumping Lemma for CFL

Five parts instead of three — the tool that marks the boundary of the context-free languages.

🌍 Where this lives: This lemma is the formal reason a compiler cannot check everything during parsing. "Every variable must be declared before use" and "the argument count must match the declaration" are both provably beyond context-free grammars by exactly this argument — they reduce to matching three or more things at once, which a single stack cannot do. That is why every compiler has a separate semantic analysis phase with a symbol table, rather than folding those checks into the parser. Search "context free pumping lemma programming language type checking limits".

Statement and the proof idea

THE PUMPING LEMMA FOR CONTEXT-FREE LANGUAGES: IF L is context free, THEN there exists a constant p ≥ 1 such that EVERY string w ∈ L with |w| ≥ p can be written as w = u v x y z satisfying ALL THREE conditions: (1) |v y| ≥ 1 v and y are not BOTH empty (2) |v x y| ≤ p the pumped parts and what lies between them fit in a window of width p (3) u vⁱ x yⁱ z ∈ L for ALL i ≥ 0 ── COMPARE THE REGULAR VERSION ───────────────────────────── REGULAR CONTEXT FREE ──────────────────────────────────────────────────────── split into THREE: x y z FIVE: u v x y z what pumps ONE piece (y) TWO pieces, v and y, IN LOCKSTEP constraint |xy| ≤ p — the |vxy| ≤ p — the pumped pumped part is parts are CLOSE near the START TOGETHER, but may be anywhere in the string underlying a repeated STATE a repeated VARIABLE on a reason in the DFA root-to-leaf path of the parse tree ──────────────────────────────────────────────────────── THE TWO PUMPED PIECES ARE THE ESSENTIAL DIFFERENCE. A context-free language CAN maintain one matched pair of counts — v and y grow together — WHICH IS EXACTLY WHY aⁿbⁿ IS CONTEXT FREE while it was not regular. ── WHY IT IS TRUE ────────────────────────────────────────── Take a grammar for L in CHOMSKY NORMAL FORM, so every parse tree is BINARY. A binary tree of height h has at most 2^h leaves, so a string of length greater than 2^h forces a tree of height greater than h. Let the grammar have m variables and set p = 2^m + 1. Any w ∈ L with |w| ≥ p has a parse tree of height at least m + 1, so SOME ROOT-TO-LEAF PATH CONTAINS MORE THAN m INTERNAL NODES — and by the PIGEONHOLE PRINCIPLE, two of them carry the SAME VARIABLE A. S / \ / \ u A ← the upper occurrence / \ v \ A ← the lower occurrence / \ x y \ z THE SUBTREE ROOTED AT THE UPPER A DERIVES v x y. THE SUBTREE ROOTED AT THE LOWER A DERIVES x. So A ⇒* v A y and A ⇒* x. THEREFORE A ⇒* vⁱ x yⁱ FOR EVERY i ≥ 0, by repeating or skipping the section between the two occurrences — WHICH IS EXACTLY CONDITION (3). · Condition (1) holds because CNF has no ε-productions, so the extra subtree cannot be empty. · Condition (2) holds because the repetition can be found within the bottom m+1 levels of the tree, bounding the yield of the upper A. THE PARALLEL WITH THE REGULAR CASE IS EXACT: THERE, A LONG STRING FORCED A REPEATED STATE, GIVING A LOOP THAT COULD BE TRAVERSED ANY NUMBER OF TIMES. HERE, A LONG STRING FORCES A REPEATED VARIABLE, GIVING A SUBTREE THAT CAN BE NESTED ANY NUMBER OF TIMES. ── THE WORKED PROOF: aⁿbⁿcⁿ IS NOT CONTEXT FREE ──────────── THE STANDARD EXAMPLE, and the one to be able to reproduce. CLAIM: L = { aⁿbⁿcⁿ : n ≥ 1 } is not context free. PROOF. Suppose it is. Let p be the pumping length. CHOOSE w = aᵖ bᵖ cᵖ. Then w ∈ L and |w| = 3p ≥ p. By condition (2), |vxy| ≤ p. THE STRING CONSISTS OF THREE BLOCKS EACH OF LENGTH p, SO A WINDOW OF WIDTH AT MOST p CAN TOUCH AT MOST TWO ADJACENT BLOCKS — it can never contain both an a and a c, because those are at least p symbols apart. TWO CASES, and both fail: CASE 1 — vxy lies within a SINGLE block. Then pumping with i = 2 increases the count of exactly ONE symbol and leaves the other two unchanged. The three counts no longer agree, so u v² x y² z ∉ L. CASE 2 — vxy SPANS TWO ADJACENT BLOCKS (a's and b's, or b's and c's). Then pumping affects at most those two symbols, and THE THIRD BLOCK IS UNTOUCHED. Again the counts disagree. Since |vy| ≥ 1 guarantees at least one symbol really is pumped, every case gives a contradiction with condition (3). Hence L is not context free. ∎ CONCRETELY, with p = 3 and w = aaabbbccc: · v = a, y = b → i = 2 gives aaaa bbbb ccc, counts 4, 4, 3 ✗ · v = b, y = c → i = 2 gives aaa bbbb cccc, counts 3, 4, 4 ✗ THE THIRD COUNT ALWAYS BETRAYS IT — which is precisely the "a stack compares two things, not three" limitation stated in the PDA topic, now proved.

More applications, and the limits

── OTHER NON-CONTEXT-FREE LANGUAGES ──────────────────────── With the string to choose in each case: { aⁿbⁿcⁿ } w = aᵖbᵖcᵖ { ww : w ∈ Σ* } w = aᵖbᵖaᵖbᵖ { aⁱbʲcᵏ : i < j < k } w = aᵖb^(p+1)c^(p+2) { aⁿ : n is prime } w = a^q, q prime and q > p { aⁿbᵐcⁿdᵐ } w = aᵖbᵖcᵖdᵖ (CROSSED dependencies) { aⁿ² : n ≥ 1 } w = a^(p²) THE { ww } CASE DESERVES ATTENTION, since the choice of w matters greatly. Taking w = aᵖaᵖ is a MISTAKE — it can be pumped, because aᵖaᵖ = a²ᵖ and pumping any two a's keeps it in the form of a doubled string when the count stays even. TAKING w = aᵖbᵖaᵖbᵖ FORCES THE ISSUE: the window of width p cannot reach both copies of any block, so pumping breaks the correspondence between the first half and the second. THE LESSON IS THE SAME AS AT THE REGULAR LEVEL — THE CHOICE OF w IS THE WHOLE PROOF. THE CROSSED DEPENDENCY CASE { aⁿbᵐcⁿdᵐ } is the linguistically important one: the a's match the c's and the b's match the d's, and the pairs INTERLEAVE. A stack can nest dependencies but cannot cross them, which is why this language is not context free while the nested version { aⁿbᵐdᵐcⁿ } is. ── THE SAME LOGICAL CAVEAT ───────────────────────────────── THE LEMMA IS NECESSARY, NOT SUFFICIENT. CONTEXT FREE ⟹ PUMPABLE. PUMPABLE ⟹ CONTEXT FREE IS **FALSE**. So the lemma can prove a language is NOT context free and can never prove that one IS. There exist non-context-free languages satisfying the lemma, exactly as at the regular level. THE STRONGER TOOL IS OGDEN'S LEMMA, which strengthens the pumping lemma by letting the prover MARK p positions in advance and requiring that the pumped parts include marked positions. That extra control defeats some languages the plain lemma cannot handle — for instance { aⁱbʲcᵏdˡ : i = 0 or j = k = l }, which is pumpable but not context free. ── USING THE CLOSURE PROPERTIES INSTEAD ──────────────────── OFTEN THE FASTEST ROUTE, and worth having as an alternative technique. Recall that CFLs are closed under INTERSECTION WITH A REGULAR LANGUAGE but NOT under intersection generally. TO SHOW L = { w ∈ {a,b,c}* : w has equal numbers of a, b and c } IS NOT CONTEXT FREE: Intersect with the regular language a*b*c*: L ∩ a*b*c* = { aⁿbⁿcⁿ } If L were context free, this intersection would be too — but we have just proved it is not. Hence L is not context free. ∎ THIS AVOIDS A CASE ANALYSIS ENTIRELY, and questions often reward it. ── THE PLACE OF THE RESULT ───────────────────────────────── The two pumping lemmas mark the two boundaries established so far: REGULAR ──(aⁿbⁿ)── CONTEXT FREE ──(aⁿbⁿcⁿ)── CONTEXT SENSITIVE AND THE REASON EACH BOUNDARY SITS WHERE IT DOES IS THE MEMORY MODEL: · a finite automaton has NO unbounded memory → it cannot count at all · a PDA has ONE stack, read last-in-first-out → it can match ONE nested pair · a linear bounded automaton has a full tape → it can compare any number of counts EVERY SEPARATION IN THE CHOMSKY HIERARCHY IS ULTIMATELY A STATEMENT ABOUT WHAT KIND OF MEMORY THE MACHINE HAS, and the pumping lemmas are how that intuition is turned into proof.

The parallel with the regular case is exact: there, a long string forced a repeated state, giving a loop that could be traversed any number of times. Here, a long string forces a repeated variable on a root-to-leaf path, giving a subtree that can be nested any number of times.

🌍 Go further: Crossed dependencies are why this lemma matters to linguistics as well as compilers. The language {aⁿbᵐcⁿdᵐ} — where the a's match the c's and the b's match the d's, interleaved — is not context free, while the nested version {aⁿbᵐdᵐcⁿ} is. A stack can nest dependencies but cannot cross them. Swiss German famously contains genuine crossed dependencies in subordinate clauses, and this observation was used in the 1980s to argue that natural language is not context free — one of the few times a pumping-lemma argument settled a debate about human languages rather than formal ones. Search "Swiss German cross-serial dependencies not context free Shieber".

💡 Exam angle: state the lemma with the five-part split and all three conditions, and be able to compare it with the regular version — three parts versus five, one pumped piece versus two. Give the parse tree justification: CNF makes trees binary, a long string forces a deep tree, and pigeonhole forces a repeated variable. The guaranteed question is proving aⁿbⁿcⁿ is not context free — choose w = aᵖbᵖcᵖ, argue that |vxy| ≤ p confines the window to at most two adjacent blocks, then give both cases. Know that the lemma is necessary but not sufficient, mention Ogden's lemma, and be ready to use intersection with a regular language as a shortcut.

Syllabus points

Statement of the lemma
Proving a language is not context-free

Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.