Pumping lemma for CFLs

WHY it is true (derivation from first principles)

Step-by-step derivation.

Convert the CFG to CNF with $b$ variables. Choose pumping length $p = 2^{b}+1$ . Why this step? CNF makes the parse tree binary, so we can bound leaf count by tree height cleanly. Taking $p$ strictly greater than $2^{b}$ guarantees the strict inequality we need in Step 2.
Take $w \in L$ with $|w| \ge p = 2^{b}+1$ , so $|w| > 2^{b}$ . A binary parse tree with more than $2^{b}$ leaves must have height $> b$ (since height $\le b$ allows at most $2^{b}$ leaves). Hence some root-to-leaf path passes through at least $b+1$ variable nodes. Why this step? Long string ⇒ more than $2^{b}$ leaves ⇒ strictly tall tree. The strict " $>2^b$ " is exactly why we set $p=2^b+1$ .
That path has $\ge b+1$ variable nodes but only $b$ distinct variables exist, so by pigeonhole two nodes on the path carry the same variable $A$ . Pick the two lowest such occurrences. Why this step? Picking the lowest pair keeps the lower subtree small — this gives condition $|vxy| \le p$ .
Let the upper $A$ derive substring $vxy$ and the lower $A$ derive substring $x$ . Then the whole string splits as $w = u\,(vxy)\,z = uvxyz$ , where the upper $A$ gives $A \Rightarrow^* vAy \Rightarrow^* vxy$ . Why this step? The recursive structure $A \Rightarrow^* vAy$ is exactly the loop we can repeat.

Justifying the three conditions:

$|vy|\ge 1$ : in CNF a node $A \to BC$ produces two children, so the upper $A$ 's subtree is strictly larger than the lower $A$ 's subtree; the extra symbols are exactly $v$ and $y$ , so they can't both be empty. (CNF has no unit/epsilon rules causing $A\Rightarrow A$ .)
$|vxy|\le p$ : we picked the two lowest repeated variables, so the subtree rooted at the upper $A$ has height $\le b+1$ , hence at most $2^{b+1}$ leaves; choosing the lowest repeat keeps this within the bound used to set $p$ (standard treatments take $p=2^{b+1}$ to make $|vxy|\le p$ exact — the key point is the lower subtree is bounded by a constant depending only on $b$ ).
$uv^i xy^i z \in L$ : by repeating/removing the loop subtree as shown.

HOW to use it (to prove a language is NOT a CFL)

It's a game / proof by contradiction:

Worked example

$L = \{a^i b^j c^k : i \le j \le k\}$ is NOT a CFL

Choose $w = a^p b^p c^p$ (satisfies $p\le p\le p$ , so $w\in L$ ). Here $i=j=k=p$ .
$vxy$ $v x y$ spans at most two letter types (length bound $|vxy|\le p$ $∣ v x y ∣ \leq p$ ).
- If it omits $c$ (so $vy$ contains only $a$ 's and/or $b$ 's): pump up ( $i=2$ ). This increases the $a$ -count or $b$ -count above $p$ , while the $c$ -count stays $p$ . So we get $j>p$ or $i>p$ with $k=p$ , making $j\le k$ or $i\le j$ fail (a letter before $c$ now exceeds $c$ ). ⇒ contradiction.
- If it omits $a$ (so $vy$ contains only $b$ 's and/or $c$ 's): pump down ( $i=0$ ). Removing at least one $b$ or $c$ makes $j<p$ or $k<p$ , while the $a$ -count stays exactly $p$ . So we get $i=p$ but $j<p$ or $k<p$ , making $i\le j$ or $j\le k$ fail. ⇒ contradiction. Why two cases? We must beat every split; if $vy$ avoids $c$ we push counts up, if it avoids $a$ we push counts down. (Note: $i$ here is the pump exponent, not the count of $a$ 's — don't confuse them with the $i$ in $a^i b^j c^k$ .)
Contradiction. ∴ not a CFL. ∎

Comparison map

Intuition Regular vs Context-Free pumping

	Regular PL	CFL PL
Split	$w=xyz$	$w=uvxyz$
Pumped pieces	one ( $y$ )	two ( $v,y$ ) together
Length bound	$	xy
Underlying object	DFA loop (cycle)	repeated variable (parse-tree subtree)
Pump rule	$xy^iz\in L$	$uv^ixy^iz\in L$

Flashcards

What does the CFL pumping lemma split a long string into?

w=uvxyz

with two pump pieces

v

and

y

What are the three conditions of the CFL pumping lemma?

(1)

|vy|\ge1

, (2)

|vxy|\le p

, (3)

uv^ixy^iz\in L

for all

i\ge0

Why are there TWO pumped pieces

v,y

in CFL PL but one in regular PL?

A repeated variable derives

A\Rightarrow^* vAy

, adding symbols on both sides of the subtree; a DFA cycle adds one contiguous segment. :::

What normal form is used to prove the CFL pumping lemma and why?

Chomsky Normal Form — it makes the parse tree binary so leaf-count vs height bounds work cleanly. :::

What principle forces a variable to repeat on a path?

Pigeonhole: a long string ⇒ tall binary parse tree ⇒ path with more variable nodes than there are distinct variables. :::

Why must the chosen string length exceed

2^{b}

(not just equal it)?

A binary tree of height

\le b

holds at most

2^{b}

leaves; only

|w|>2^{b}

forces height

>b

and hence a repeated variable, so we set

p=2^b+1

. :::

In the proof game, who chooses

p

w

, the split, and

i

Adversary chooses

p

and the split; you choose

w

and

i

. :::

Why does

|vxy|\le p

matter for proving

a^nb^nc^n

is not a CFL?

It forces

vxy

to touch at most two letter blocks, so pumping unbalances the counts. :::

Can the pumping lemma prove a language IS context-free?

No — it only proves a language is NOT context-free (necessary, not sufficient). :::

Good witness string for showing

L=\{a^nb^nc^n\}

not CFL?

w=a^pb^pc^p

, then pump

i=2

. :::

Good witness string for

\{ww\}

not CFL?

0^p1^p0^p1^p

. :::

Why pick the two LOWEST repeated variables on the path?

To bound the lower subtree size, guaranteeing

|vxy|\le p

. :::

Recall Feynman: explain to a 12-year-old

Imagine a family tree that makes words. If the word is really long, the tree is really tall, and somewhere on the way down a name has to repeat (there are only so many names!). Wherever a name repeats, you've found a loop — like a verse you can sing 0, 1, 2, or 100 times. So every super-long word in the language has a part you can repeat, and the repeat adds stuff on the left AND right at the same time (because the tree branches). If you find a long word where no repeat can be added without breaking the rules, the language is too clever to be made by such a tree — it's not context-free.

Connections

Context-Free Grammars — the loop $A\Rightarrow^* vAy$ comes from grammar recursion.
Chomsky Normal Form — the binary-tree machinery behind the proof.
Pumping lemma for regular languages — single-piece analogue; same pigeonhole spirit.
Parse Trees and Derivations — pumping = duplicating a subtree.
Closure properties of CFLs — combine with closure to extend non-CFL proofs.
Pushdown Automata — equivalent machine model; stack ↔ recursion.
Pigeonhole Principle — the core counting argument.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, CFL pumping lemma ka core idea bahut simple hai. Har context-free language ke peeche ek grammar (CFG) hoti hai. Jab string bahut lambi ho jaati hai, to uska parse tree itna tall ho jaata hai ki kisi ek path par koi variable (non-terminal) repeat zaroor karega — pigeonhole principle ki wajah se, kyunki variables to limited (sirf $b$ ) hain. Important detail: agar string ki length $2^b$ se strictly zyada ho, tabhi tree itna tall banega; isliye $p=2^b+1$ lete hain. Yahi repeat ek loop hai: $A \Rightarrow^* vAy$ . Is loop ko hum 0, 1, 2, ya jitni baar chaaho pump kar sakte hain, aur string language mein hi rahegi.

Yaad rakhna sabse important difference: regular languages mein ek hi piece pump hota tha ( $xy^iz$ ), lekin CFL mein do pieces $v$ aur $y$ ek saath, same exponent $i$ ke saath pump hote hain ( $uv^ixy^iz$ ). Iska reason yeh hai ki parse tree branch karta hai — repeating variable ke neeche ka material left side ( $v$ ) aur right side ( $y$ ) dono par aata hai. Conditions yaad rakho: $|vy|\ge1$ (dono khaali nahi), $|vxy|\le p$ (window chhoti), aur pump sab $i\ge0$ ke liye chale.

Yeh lemma kis kaam aata hai? Kisi language ko NOT context-free prove karne ke liye — contradiction se. Yeh ek game hai: adversary tumhe $p$ deta hai, tum ek smart string $w$ (length $\ge p$ ) choose karte ho, adversary koi bhi valid split deta hai, aur tum aisa $i$ (aksar $0$ ya $2$ ) choose karte ho ki string language se bahar nikal jaaye. Classic example $a^nb^nc^n$ hai: $w=a^pb^pc^p$ lo, $|vxy|\le p$ ki wajah se window sirf do blocks ko touch kar sakti hai, pump karo to teen counts barabar nahi rahenge — contradiction! Dhyaan rahe: $\{a^ib^jc^k: i\le j\le k\}$ wale example mein " $i$ " do matlab rakhta hai — ek pump exponent, ek $a$ ka count; in dono ko mat mila dena.

Ek warning: pumping lemma se tum kabhi yeh prove nahi kar sakte ki language CFL hai (yeh sirf necessary condition hai). CFL prove karne ke liye grammar ya PDA banao. Aur string choose karte waqt sabse tough, sabse constrained string lo, warna adversary aaram se pump kar lega aur tumhara proof fail ho jaayega.

WHAT it says

WHY it is true (derivation from first principles)

HOW to use it (to prove a language is NOT a CFL)

Comparison map

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Theory of Computation

Connections