Pumping lemma for CFLs

4.6.12 · Coding › Theory of Computation

WHY it is true (derivation from first principles)

Step-by-step derivation.

CFG ko CNF mein convert karo jisme $b$ variables hain. Pumping length $p = 2^{b} + 1$ choose karo. Yeh step kyun? CNF parse tree ko binary banata hai, isliye hum tree height se leaf count ko cleanly bound kar sakte hain. $p$ ko strictly greater than $2^{b}$ lena Step 2 mein zaroori strict inequality guarantee karta hai.
$w \in L$ lo jisme $∣ w ∣ \geq p = 2^{b} + 1$ ho, toh $∣ w ∣ > 2^{b}$ . Ek binary parse tree jisme $2^{b}$ se zyada leaves hain, uski height $> b$ honi chahiye (kyunki height $\leq b$ mein at most $2^{b}$ leaves hoti hain). Isliye koi root-to-leaf path at least $b + 1$ variable nodes se guzarta hai. Yeh step kyun? Lambi string ⇒ $2^{b}$ se zyada leaves ⇒ strictly tall tree. Yeh strict " $> 2^{b}$ " exactly wahi reason hai jiske liye humne $p = 2^{b} + 1$ set kiya.
Us path mein $\geq b + 1$ variable nodes hain lekin sirf $b$ distinct variables exist karte hain, isliye pigeonhole se path par do nodes par same variable $A$ hai. Do lowest aisi occurrences choose karo. Yeh step kyun? Lowest pair choose karne se lower subtree chhota rehta hai — isse condition $∣ v x y ∣ \leq p$ milti hai.
Upper $A$ ko substring $v x y$ derive karne do aur lower $A$ ko substring $x$ derive karne do. Tab poori string split hoti hai $w = u (v x y) z = uv x y z$ , jahan upper $A$ deta hai $A \Rightarrow^{*} v A y \Rightarrow^{*} v x y$ . Yeh step kyun? Recursive structure $A \Rightarrow^{*} v A y$ exactly woh loop hai jo hum repeat kar sakte hain.

Teeno conditions justify karna:

$∣ v y ∣ \geq 1$ : CNF mein ek node $A \to B C$ do children produce karta hai, toh upper $A$ ka subtree strictly larger hota hai lower $A$ ke subtree se; extra symbols exactly $v$ aur $y$ hain, toh woh dono empty nahi ho sakte. (CNF mein unit/epsilon rules nahi hote jo $A \Rightarrow A$ cause karein.)
$∣ v x y ∣ \leq p$ : humne do lowest repeated variables choose kiye, toh upper $A$ rooted subtree ki height $\leq b + 1$ hai, isliye at most $2^{b + 1}$ leaves hain; lowest repeat choose karna isse us bound ke andar rakhta hai jo $p$ set karne ke liye use hui hai (standard treatments $p = 2^{b + 1}$ lete hain taaki $∣ v x y ∣ \leq p$ exact ho — key point yeh hai ki lower subtree sirf $b$ par depend karne wale ek constant se bounded hai).
$u v^{i} x y^{i} z \in L$ : loop subtree ko dikhaye gaye tarike se repeat/remove karke.

HOW to use it (prove karne ke liye ki language NOT a CFL hai)

Yeh ek game / proof by contradiction hai:

Worked example

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

Choose karo $w = a^{p} b^{p} c^{p}$ ( $p \leq p \leq p$ satisfy karta hai, toh $w \in L$ ). Yahan $i = j = k = p$ .
$v x y$ at most do letter types span karta hai (length bound $∣ v x y ∣ \leq p$ ).
- Agar yeh $c$ omit kare (toh $v y$ mein sirf $a$ 's aur/ya $b$ 's hain): upar pump karo ( $i = 2$ ). Isse $a$ -count ya $b$ -count $p$ se upar chali jaati hai, jabki $c$ -count $p$ rehta hai. Toh hume $j > p$ ya $i > p$ milta hai jisme $k = p$ ho, $j \leq k$ ya $i \leq j$ fail ho jaata hai ( $c$ se pehle wala ek letter ab $c$ se zyada ho jaata hai). ⇒ contradiction.
- Agar yeh $a$ omit kare (toh $v y$ mein sirf $b$ 's aur/ya $c$ 's hain): neeche pump karo ( $i = 0$ ). Kam se kam ek $b$ ya $c$ remove karne se $j < p$ ya $k < p$ ho jaata hai, jabki $a$ -count exactly $p$ rehta hai. Toh hume $i = p$ milta hai lekin $j < p$ ya $k < p$ , $i \leq j$ ya $j \leq k$ fail ho jaata hai. ⇒ contradiction. Do cases kyun? Humein har split ko beat karna hai; agar $v y$ $c$ se bachta hai toh counts upar push karo, agar $a$ se bachta hai toh counts neeche push karo. (Note: yahan $i$ pump exponent hai, $a$ 's ki count nahi — ise $a^{i} b^{j} c^{k}$ wale $i$ se confuse mat karo.)
Contradiction. ∴ CFL nahi hai. ∎

Comparison map

Intuition Regular vs Context-Free pumping

	Regular PL	CFL PL
Split	$w = x y z$	$w = uv x y z$
Pumped pieces	ek ( $y$ )	do ( $v, y$ ) saath mein
Length bound	$	xy
Underlying object	DFA loop (cycle)	repeated variable (parse-tree subtree)
Pump rule	$x y^{i} z \in L$	$u v^{i} x y^{i} z \in L$

Flashcards

CFL pumping lemma ek lambi string ko kya split karta hai?

w = uv x y z

jisme do pump pieces

v

aur

y

hain.

CFL pumping lemma ki teeno conditions kya hain?

(1)

∣ v y ∣ \geq 1

, (2)

∣ v x y ∣ \leq p

, (3)

u v^{i} x y^{i} z \in L

sabhi

i \geq 0

ke liye.

CFL PL mein TWO pumped pieces

v, y

kyun hain lekin regular PL mein ek hi?

Ek repeated variable derive karta hai

A \Rightarrow^{*} v A y

, subtree ke dono sides par symbols add karte hue; ek DFA cycle ek contiguous segment add karta hai. :::

CFL pumping lemma prove karne ke liye kaun sa normal form use hota hai aur kyun?

Chomsky Normal Form — yeh parse tree ko binary banata hai taki leaf-count vs height bounds cleanly kaam karein. :::

Kaun sa principle ek path par variable ko repeat hone force karta hai?

Pigeonhole: lambi string ⇒ tall binary parse tree ⇒ path jisme variable nodes ki sankhya distinct variables se zyada ho. :::

Chosen string length

2^{b}

se kyun exceed karni chahiye (sirf equal nahi)?

Height

\leq b

wala binary tree at most

2^{b}

leaves hold karta hai; sirf

∣ w ∣ > 2^{b}

height

> b

force karta hai aur isliye ek repeated variable, toh hum

p = 2^{b} + 1

set karte hain. :::

Proof game mein

p

w

, split, aur

i

kaun choose karta hai?

Adversary

p

aur split choose karta hai; tum

w

aur

i

choose karte ho. :::

∣ v x y ∣ \leq p

kyun matter karta hai

a^{n} b^{n} c^{n}

ke not CFL hone ke liye prove karne mein?

Yeh

v x y

ko at most do letter blocks touch karne par force karta hai, toh pumping counts unbalance kar deta hai. :::

Kya pumping lemma prove kar sakta hai ki language IS context-free hai?

Nahi — yeh sirf prove karta hai ki language NOT context-free hai (necessary, sufficient nahi). :::

L = {a^{n} b^{n} c^{n}}

ke not CFL hone ke liye achi witness string?

w = a^{p} b^{p} c^{p}

, phir

i = 2

pump karo. :::

{w w}

ke not CFL hone ke liye achi witness string?

0^{p} 1^{p} 0^{p} 1^{p}

. :::

Path par do LOWEST repeated variables kyun choose karte hain?

Lower subtree size bound karne ke liye,

∣ v x y ∣ \leq p

guarantee karne ke liye. :::

Recall Feynman: 12-saal ke bachche ko samjhao

Ek family tree imagine karo jo words banata hai. Agar word bahut lamba hai, tree bahut tall hai, aur kahin neeche jaate waqt ek naam repeat hona hi padega (kitne hi naam hote hain!). Jahan bhi naam repeat hota hai, tumne ek loop dhundh liya — jaise ek verse jo tum 0, 1, 2, ya 100 baar ga sakte ho. Toh language ki har super-long word mein ek part hota hai jise tum repeat kar sakte ho, aur repeat left AUR right dono par ek saath kuch add karta hai (kyunki tree branch karta hai). Agar tumhe ek lambi word milti hai jahan koi bhi repeat rules tode bina add nahi ho sakta, language itni smart hai ki aisi tree se nahi ban sakti — woh not context-free hai.

Connections

Context-Free Grammars — loop $A \Rightarrow^{*} v A y$ grammar recursion se aata hai.
Chomsky Normal Form — proof ke peeche binary-tree machinery.
Pumping lemma for regular languages — single-piece analogue; same pigeonhole spirit.
Parse Trees and Derivations — pumping = ek subtree duplicate karna.
Closure properties of CFLs — non-CFL proofs extend karne ke liye closure ke saath combine karo.
Pushdown Automata — equivalent machine model; stack ↔ recursion.
Pigeonhole Principle — core counting argument.

WHAT it says