Pumping Lemma for Regular Languages

What is the Pumping Lemma?

Pumping Lemma is a fundamental theorem that helps us prove a language is NOT regular. It states a necessary condition that all regular languages must satisfy.

Simple Analogy

Think of the Pumping Lemma like a detective test:

• If a language is regular
• Then it must pass the pumping test
• If it fails the test → NOT regular

Important: Pumping Lemma is a one-way test:

• ✓ Can prove a language is NOT regular
• ✗ Cannot prove a language IS regular

Why Do We Need It?

Problem: How to prove a language is NOT regular?

Bad approaches:

• ✗ “I can’t find a DFA” → Maybe you didn’t try hard enough
• ✗ “It looks complicated” → Not a proof

Good approach:

• ✓ Use Pumping Lemma to show it violates a necessary condition

The Pumping Lemma Statement

Pumping Lemma for Regular Languages:

If L is a regular language, then there exists a constant p (pumping length) such that:

For any string w ∈ L where |w| ≥ p, we can write w = xyz satisfying:

1. |xy| ≤ p (y is in the first p symbols)
2. |y| ≥ 1 (y is non-empty)
3. xyⁱz ∈ L for all i ≥ 0 (can pump y any number of times)

Breaking Down the Statement

p (pumping length):

• A constant that depends on the language
• Typically p = number of states in minimal DFA
• We don’t know p, but we know it exists

w = xyz (decomposition):

• Split string into three parts
• x: prefix
• y: pumpable part (the “pump”)
• z: suffix

Three conditions:

1. |xy| ≤ p: The pumpable part is near the beginning
2. |y| ≥ 1: Must pump something (y can’t be empty)
3. xyⁱz ∈ L: Pumping y keeps string in L

Intuition Behind the Lemma

Why must regular languages have this property?

DFA with n states:

• Reading string of length ≥ n
• Must visit ≥ n+1 states (including start)
• By Pigeonhole Principle: Some state visited twice!
• Can loop between repeated state (this is y)
• Loop 0 times, 1 time, 2 times, … all accepted

Visual:

     x          y           z
q₀ ────→ qᵢ ────→ qᵢ ────→ qf
           ↺ (loop)

Can repeat loop: xy⁰z, xy¹z, xy²z, xy³z, ...
All must be in L!

Proof of Pumping Lemma

Given: L is regular, accepted by DFA M with n states

Let: p = n (pumping length)

Take: Any w ∈ L with |w| ≥ p

Process w in M:

w = a₁a₂a₃...aₘ where m ≥ p

State sequence: q₀, q₁, q₂, ..., qₘ
(m+1 states visited)

By Pigeonhole Principle:

• First p+1 states: q₀, q₁, …, qₚ
• But only p distinct states available
• So ∃i, j where 0 ≤ i < j ≤ p and qᵢ = qⱼ

Decompose w:

x = a₁...aᵢ (prefix to first occurrence)
y = aᵢ₊₁...aⱼ (loop part)
z = aⱼ₊₁...aₘ (suffix)

Verify conditions:

1. |xy| = j ≤ p ✓
2. |y| = j - i ≥ 1 ✓ (since i < j)
3. xyⁱz ∈ L ✓ (can repeat loop i times)

QED ∎

Using Pumping Lemma (Contrapositive)

Contrapositive of Pumping Lemma:

If for all p ≥ 1, there exists w ∈ L with |w| ≥ p such that:

For all decompositions w = xyz satisfying conditions 1 and 2, there exists i ≥ 0 where xyⁱz ∉ L

Then L is NOT regular.

Proof Strategy (Game Theory Approach)

Think of it as a game with an adversary:

1. Adversary picks p (pumping length)
2. You pick w ∈ L where |w| ≥ p
3. Adversary picks decomposition w = xyz (satisfying conditions 1, 2)
4. You pick i such that xyⁱz ∉ L

If you can always win (step 4), then L is NOT regular!

General Proof Template

Proof that L is not regular:

1. Assume L is regular (for contradiction)
2. Let p be the pumping length
3. Choose w = [some string in L with length ≥ p]
4. Consider any decomposition w = xyz with |xy| ≤ p, |y| ≥ 1
5. Show that for some i, xyⁱz ∉ L
6. Contradiction! Therefore L is not regular.

Classic Examples

Example 1: L = {0ⁿ1ⁿ | n ≥ 0}

Language: Equal number of 0’s and 1’s in sequence

Proof that L is NOT regular:

Step 1: Assume L is regular

Step 2: Let p be the pumping length

Step 3: Choose w = 0⁽1⁽ (p zeros followed by p ones)

• Clearly w ∈ L
• |w| = 2p ≥ p ✓

Step 4: Consider any decomposition w = xyz with |xy| ≤ p, |y| ≥ 1

Key observation: Since |xy| ≤ p, both x and y consist only of 0’s!

• w = 0…0 0…0 1…1

•   └x─┘ └y─┘ └z─┘

Step 5: Consider i = 2 (pump twice)

• xy²z = xyyz
• y consists only of 0’s, say |y| = k where 1 ≤ k ≤ p
• xy²z has p + k zeros and p ones
• p + k > p, so unequal numbers → xy²z ∉ L ✗

Step 6: Contradiction! Therefore L is NOT regular. ∎

Example 2: L = {0ⁿ | n is prime}

Language: Strings of 0’s where length is prime number

Proof that L is NOT regular:

Step 1: Assume L is regular

Step 2: Let p be the pumping length

Step 3: Choose w = 0ⁿ where q is prime and q ≥ p

• w ∈ L
• |w| = q ≥ p ✓

Step 4: Consider any decomposition w = xyz with |xy| ≤ p, |y| ≥ 1

• Let |y| = k where 1 ≤ k ≤ p

Step 5: Consider i = q + 1

• xyⁿ⁺¹z = x y^{q+1} z
• |xyⁿ⁺¹z| = |w| + k·q = q + kq = q(1 + k)
• Since k ≥ 1, we have 1 + k ≥ 2
• So q(1 + k) is composite (not prime)
• Therefore xyⁿ⁺¹z ∉ L ✗

Step 6: Contradiction! Therefore L is NOT regular. ∎

Example 3: L = {ww | w ∈ {0,1}*}

Language: Strings that are repetitions of themselves

Examples: ε, 00, 11, 0101, 1111, 001001, …

Proof that L is NOT regular:

Step 1: Assume L is regular

Step 2: Let p be the pumping length

Step 3: Choose w = 0⁽1⁽0⁽1⁽ (0⁽1⁽ repeated twice)

• w ∈ L
• |w| = 4p ≥ p ✓

Step 4: Consider any decomposition w = xyz with |xy| ≤ p, |y| ≥ 1

• Since |xy| ≤ p, both x and y are in the first 0⁽ part
• y consists only of 0’s

Step 5: Consider i = 2

• xy²z has more 0’s in first half than second half
• Cannot be of form ww anymore
• xy²z ∉ L ✗

Step 6: Contradiction! Therefore L is NOT regular. ∎

Example 4: L = {0ⁿ1ᵐ | n > m}

Language: More 0’s than 1’s

Proof that L is NOT regular:

Step 1: Assume L is regular

Step 2: Let p be the pumping length

Step 3: Choose w = 0⁽⁺¹1⁽

• n = p + 1, m = p, so n > m ✓
• w ∈ L
• |w| = 2p + 1 ≥ p ✓

Step 4: Consider any decomposition w = xyz with |xy| ≤ p, |y| ≥ 1

• y consists only of 0’s

Step 5: Consider i = 0 (pump zero times)

• xz has p + 1 - |y| zeros and p ones
• Since |y| ≥ 1, we have p + 1 - |y| ≤ p
• If |y| = 1: p zeros and p ones (equal, not n > m)
• If |y| > 1: fewer than p zeros and p ones (n < m)
• Either way: xz ∉ L ✗

Step 6: Contradiction! Therefore L is NOT regular. ∎

Example 5: L = {aⁿbᶜ | n = c²}

Language: n is a perfect square, then c copies of b

Examples: b, a⁴b², a⁹b³, a¹⁶b⁴, …

Proof that L is NOT regular:

Step 1: Assume L is regular

Step 2: Let p be the pumping length

Step 3: Choose w = a⁽²b⁽

• w ∈ L (p² is perfect square, √p² = p)
• |w| = p² + p ≥ p ✓

Step 4: Consider any decomposition w = xyz with |xy| ≤ p, |y| ≥ 1

• y consists only of a’s
• Let |y| = k where 1 ≤ k ≤ p

Step 5: Consider i = 2

• xy²z = a⁽²⁺kb⁽
• Need p² + k to be perfect square
• But p² < p² + k < p² + 2p + 1 = (p+1)²
• No perfect square between p² and (p+1)²!
• xy²z ∉ L ✗

Step 6: Contradiction! Therefore L is NOT regular. ∎

Example 6: L = {0ⁿ1ᵐ | n ≠ m}

Language: Unequal number of 0’s and 1’s

Proof that L is NOT regular:

Step 1: Assume L is regular

Step 2: Let p be the pumping length

Step 3: Choose w = 0⁽1⁽⁺¹

• n = p, m = p + 1, so n ≠ m ✓
• w ∈ L
• |w| = 2p + 1 ≥ p ✓

Step 4: Consider any decomposition w = xyz with |xy| ≤ p, |y| ≥ 1

• y consists only of 0’s
• Let |y| = k where 1 ≤ k ≤ p

Step 5: Consider i where xyⁱz has equal 0’s and 1’s

• Choose i such that p - k + ik = p + 1
• Solving: ik = 1 + k, so i = 1 + 1/k
• If k = 1, then i = 2 works!
• xy²z = 0⁽⁺¹1⁽⁺¹ (equal numbers)
• xy²z ∉ L ✗

Step 6: Contradiction! Therefore L is NOT regular. ∎

Example 7: L = {w | w has equal number of 0’s and 1’s}

Language: Equal count of 0’s and 1’s (any order)

Examples: ε, 01, 10, 0011, 0101, 1100, …

Proof that L is NOT regular:

Step 1: Assume L is regular

Step 2: Let p be the pumping length

Step 3: Choose w = 0⁽1⁽

• w ∈ L
• |w| = 2p ≥ p ✓

Step 4: Consider any decomposition w = xyz with |xy| ≤ p, |y| ≥ 1

• y consists only of 0’s (since |xy| ≤ p)

Step 5: Consider i = 2

• xy²z has p + |y| zeros and p ones
• Unequal count
• xy²z ∉ L ✗

Step 6: Contradiction! Therefore L is NOT regular. ∎

Example 8: L = {aⁿbᶜ | m ≥ n}

Language: At least as many b’s as a’s

Proof that L is NOT regular:

Step 1: Assume L is regular

Step 2: Let p be the pumping length

Step 3: Choose w = a⁽b⁽

• m = n = p, so m ≥ n ✓
• w ∈ L
• |w| = 2p ≥ p ✓

Step 4: Consider any decomposition w = xyz with |xy| ≤ p, |y| ≥ 1

• y consists only of a’s

Step 5: Consider i = 2

• xy²z = a⁽⁺|y|b⁽
• Now we have p + |y| a’s and p b’s
• p + |y| > p, so more a’s than b’s
• xy²z ∉ L ✗

Step 6: Contradiction! Therefore L is NOT regular. ∎

Advanced Examples

Example 9: L = {wᵣ | w ∈ {0,1}*}

Language: Reversals of strings (palindromes of even length)

Note: This is NOT the same as palindromes! L = {ww^R}

Examples: ε, 00, 11, 0110, 1001, …

Proof that L is NOT regular:

Step 1: Assume L is regular

Step 2: Let p be the pumping length

Step 3: Choose w = 0⁽1⁽

• w^R = 1⁽0⁽
• ww^R = 0⁽1⁽1⁽0⁽ ∈ L
• |ww^R| = 4p ≥ p ✓

Step 4: Consider decomposition with |xy| ≤ p, |y| ≥ 1

• y consists only of 0’s

Step 5: Consider i = 2

• Pumping adds 0’s to first quarter only
• No longer has form ww^R
• xy²z ∉ L ✗

Step 6: Contradiction! Therefore L is NOT regular. ∎

Example 10: L = {aⁿbᶜᶜ | n ≥ 0}

Language: One a for every two b’s

Examples: ε, abb, aabbbb, aaabbbbbb, …

Proof that L is NOT regular:

Step 1: Assume L is regular

Step 2: Let p be the pumping length

Step 3: Choose w = a⁽b²⁽

• w ∈ L
• |w| = 3p ≥ p ✓

Step 4: Consider decomposition with |xy| ≤ p, |y| ≥ 1

• y consists only of a’s
• Let |y| = k

Step 5: Consider i = 2

• xy²z = a⁽⁺kb²⁽
• Need (p + k) a’s and 2(p + k) b’s for xy²z ∈ L
• But we have 2p b’s, not 2(p + k)
• xy²z ∉ L ✗

Step 6: Contradiction! Therefore L is NOT regular. ∎

Common Pitfalls

Mistake 1: Wrong Choice of w

✗ Bad: Choose w that’s too simple

L = {0ⁿ1ⁿ | n ≥ 0}
Choose w = 01

Problem: Short strings can often be pumped successfully

✓ Good: Choose w dependent on p

Choose w = 0⁽1⁽

Mistake 2: Assuming Specific Decomposition

✗ Bad: “Let y = 0⁽”

Problem: You don’t get to choose y! Adversary does.

✓ Good: “Consider ANY decomposition where |xy| ≤ p, |y| ≥ 1”

Then argue: “Since |xy| ≤ p, y must consist of…”

Mistake 3: Wrong Value of i

✗ Bad: Always use i = 0 or i = 2

Problem: Sometimes other values work better

✓ Good: Try different values:

• i = 0: Remove y
• i = 2: Double y
• i = p + 1: Often useful
• Find i algebraically

Mistake 4: Not Explaining Why xyⁱz ∉ L

✗ Bad: “xy²z ∉ L”

Problem: Need to explain why!

✓ Good: “xy²z has p + k zeros and p ones. Since k ≥ 1, this is unequal, so xy²z ∉ L.”

Mistake 5: Using Pumping Lemma to Prove Regularity

✗ Bad: “L satisfies pumping lemma, so L is regular”

Problem: Pumping Lemma is only one-way!

• Fails PL → NOT regular ✓
• Passes PL → ??? (could be regular or not)

✓ Good: Use DFA/NFA/regex to prove regularity

When Pumping Lemma Fails to Prove Non-Regularity

Some non-regular languages satisfy pumping condition!

Example: L = {aⁿ | n is not prime} ∪ {aⁿbⁿ | n ≥ 0}

This language:

• Is NOT regular
• But satisfies pumping lemma!

Why?: The aⁿbⁿ part can always be pumped

Lesson: Pumping Lemma is sufficient but not necessary

Stronger Tools

Myhill-Nerode Theorem

More powerful than Pumping Lemma:

• If index(≡ₗ) is infinite → L not regular
• Both necessary and sufficient!

Example: L = {0ⁿ1ⁿ | n ≥ 0}

Strings 0, 0², 0³, ... are all distinguishable
(need different suffixes to get into L)
Infinitely many equivalence classes
→ NOT regular

Closure Properties

Use closure under operations:

Example: If L = {0ⁿ1ⁿ} were regular, then:

L ∩ 0*1* = {0ⁿ1ⁿ} (same language)

But we can use a different approach:
- If L regular, L ∩ 0*1* regular
- But L ∩ 0*1* = {0ⁿ1ⁿ}
- Contradiction by Pumping Lemma

Summary of Strategy

Step-by-Step Guide

1. Assume L is regular (for contradiction)

2. Let p be pumping length (given by Pumping Lemma)

3. Choose string w ∈ L where |w| ≥ p

   • Usually choose w with “balanced” structure
   • Depend on p: w = 0⁽1⁽, etc.

4. Consider ANY decomposition w = xyz with |xy| ≤ p, |y| ≥ 1

   • Don’t assume specific y!
   • Use constraints to determine what y must contain

5. Choose i such that xyⁱz ∉ L

   • Try i = 0, 1, 2 first
   • May need specific i based on problem

6. Explain why xyⁱz ∉ L

   • Be explicit about violation
   • Use concrete counting/reasoning

7. Conclude: Contradiction! L is NOT regular. ∎

Important Exam Points

1. ✓ Pumping Lemma: Necessary condition for regularity
2. ✓ Three conditions: |xy| ≤ p, |y| ≥ 1, xyⁱz ∈ L for all i
3. ✓ Contrapositive: Use to prove NON-regularity
4. ✓ Choice of w: Must depend on p, usually w = s⁽ for some string s
5. ✓ Decomposition: You must consider ALL possible decompositions
6. ✓ Value of i: Choose strategically (0, 2, or specific value)
7. ✓ One-way test: Fails PL → Not regular; Passes PL → Unknown
8. ✓ Proof structure: Contradiction via game-theoretic approach
9. ✓ Common patterns: {0ⁿ1ⁿ}, {0ⁿ | n prime}, {ww}, etc.
10. ✓ Alternative: Myhill-Nerode theorem is stronger

Practice Questions

Q1: What does the Pumping Lemma prove?

Answer: It proves languages are NOT regular (one-way test).

Q2: Can Pumping Lemma prove a language IS regular?

Answer: No, it’s only a necessary condition, not sufficient.

Q3: Why choose w = 0⁽1⁽ for L = {0ⁿ1ⁿ}?

Answer: Long enough to force repetition, and balanced structure makes pumping break the balance.

Q4: Must y be in the first p symbols?

Answer: xy must be in first p symbols, so y is definitely in first p.

Q5: Can y be empty?

Answer: No, |y| ≥ 1 is a required condition.

Q6: What value of i to use for {0ⁿ1ⁿ}?

Answer: i = 2 works well (doubles y, breaking balance).

Q7: Is {0ⁿ | n ≤ 1000} regular?

Answer: Yes, it’s finite! Pumping Lemma doesn’t apply to finite languages.

Q8: Can we pump y in the middle of string?

Answer: No, condition |xy| ≤ p forces y near beginning.

Summary

• Pumping Lemma: Necessary condition for regular languages
• Statement: Long strings in regular languages must have pumpable substring near beginning
• Use: Prove languages are NOT regular (contrapositive)
• Proof Template: Assume regular → Choose w → Consider decomposition → Pick i → Show xyⁱz ∉ L → Contradiction
• Three conditions: |xy| ≤ p (early), |y| ≥ 1 (non-empty), xyⁱz ∈ L (pumpable)
• Classic examples: {0ⁿ1ⁿ}, {0ⁿ | n prime}, {ww}, equal counts
• Limitations: Only proves non-regularity, not regularity
• Alternatives: Myhill-Nerode theorem (stronger), closure properties
• Key insight: Regular languages have finite memory (states), so long strings must have repetition

Pumping Lemma is the primary tool for proving non-regularity of languages!