Pumping Lemma
Prove languages are non-regular and non-context-free
Pumping Lemma (Regular Languages)
∀ s ∈ L with |s| ≥ p, s can be written as s = xyz where:
1. |xy| ≤ p
2. |y| ≥ 1
3. xyⁱz ∈ L for all i ≥ 0
Pumping Lemma (Context-Free Languages)
∀ s ∈ L with |s| ≥ p, s = uvxyz where:
1. |vxy| ≤ p
2. |vy| ≥ 1
3. uvⁱxyⁱz ∈ L for all i ≥ 0
Interactive Proof Assistant
L = { aⁿbⁿ | n ≥ 0 }
aⁿbⁿ
L = { aⁿbⁿ | n ≥ 0 }
ww
L = { ww | w ∈ {a,b}* }
aⁿ (prime)
L = { aᵖ | p is prime }
aⁿbⁿcⁿ
L = { aⁿbⁿcⁿ | n ≥ 0 }
Key Insight
The Pumping Lemma captures the idea that any regular/context-free language has a “memory limitation.” If a language requires counting beyond what a finite automaton or PDA can track, it cannot be regular/context-free. This makes the PL a powerful tool for proving lower bounds on language complexity.
Interview Questions
Q1: State the Pumping Lemma for regular languages.
If L is a regular language, then there exists a pumping length p ≥ 1 such that every string s ∈ L with |s| ≥ p can be written as s = xyz satisfying: (1) |xy| ≤ p, (2) |y| ≥ 1, (3) xyⁱz ∈ L for all i ≥ 0. The lemma is used to prove that certain languages are not regular by contradiction.
Q2: How is the Pumping Lemma for CFLs different from the one for regular languages?
The CFL Pumping Lemma states that for any CFL L, there exists p such that any s ∈ L with |s| ≥ p can be written as s = uvxyz satisfying: (1) |vxy| ≤ p, (2) |vy| ≥ 1, (3) uvⁱxyⁱz ∈ L for all i ≥ 0. The key difference is that strings are decomposed into five parts (not three), and the pumped sections (v and y) can appear in different positions.
Q3: Why doesn't the Pumping Lemma prove a language is regular?
The Pumping Lemma is a necessary condition for regularity, not a sufficient one. If a language satisfies the PL, it might still be non-regular. The PL only provides a way to prove non-regularity: if a language fails the condition, it cannot be regular. The converse (satisfying PL ⇒ regular) is false — there exist non-regular languages that satisfy the PL.