Pumping Lemma: Proving Languages Are Not Regular

The Bouncer Problem

Imagine a nightclub bouncer with a very bad memory. He can remember his current "mood" but only one of a fixed number of moods. He has no notepad, no phone, no way to count.

Some rules he can enforce: "No one under 5'6"." "No sneakers." These are rules about the current state of the person in front of him they require only finite memory.

But some rules he cannot enforce: "The number of people inside must always equal the number of people who entered." To enforce that, he would need to count and counting requires memory that grows without bound. His finite moods are not enough.

A DFA is that bouncer. It can only remember which state it is currently in. Languages that require counting like matching equal numbers of 0s and 1s are beyond its ability. But how do we prove that no DFA can recognize such a language?

That proof tool is the Pumping Lemma.

The Core Intuition: Pigeonhole in a DFA

Recall the Pigeonhole Principle: if you have more pigeons than holes, some hole contains more than one pigeon.

Apply this to a DFA with p states processing a string w with |w| ≥ p:

• The DFA visits states as it reads each character: q₀, q₁, q₂, ..., q_{|w|}
• That is |w| + 1 ≥ p + 1 states visited
• But there are only p distinct states
• By the Pigeonhole Principle: some state must be visited at least twice

When a state is revisited, the DFA has gone around a loop. The substring read during that loop is a string y. If we repeat y any number of times (pump it), the DFA still goes around the same loop that many times and still ends in the same final state.

If the original string was accepted, then pumping y (any number of times) must also produce an accepted string. This is the pumping property.

Formal Statement

Pumping Lemma for Regular Languages:

If L is a regular language, then there exists a pumping length p ≥ 1 such that for every string w ∈ L with |w| ≥ p:

w can be split as w = xyz satisfying all three conditions:

1. |y| ≥ 1 (y is non empty there is an actual loop)
2. |xy| ≤ p (the loop occurs within the first p characters)
3. For all k ≥ 0: xy^k z ∈ L (pumping y any number of times stays in L)

Note on y^k:

• k = 0: xz (remove the loop zero repetitions)
• k = 1: xyz = w (the original string)
• k = 2: xyyz (two repetitions of the loop)
• k = 3: xyyyz, and so on

The pumping length p is the number of states in the minimum DFA for L. Any string at least as long as the number of states must trigger a loop.

How to Use the Pumping Lemma: Proof Structure

The Pumping Lemma is a statement about regular languages. To use it to prove L is NOT regular, we use proof by contradiction:

Step 1: Assume L is regular. Then the Pumping Lemma guarantees a pumping length p.

Step 2: You choose a specific string w ∈ L with |w| ≥ p. Choose strategically pick a string that will be hard to pump.

Step 3: Argue about all possible splits w = xyz satisfying |y| ≥ 1 and |xy| ≤ p. Show that for every such split, there exists some k ≥ 0 where xy^k z ∉ L.

Step 4: This contradicts condition 3 of the Pumping Lemma. Therefore, L is not regular.

Common mistake: Choosing a specific split and showing it fails. You must show all possible splits fail. You get to choose w; the Pumping Lemma chooses the split (adversarially). You must defeat every possible adversarial split.

Classic Example 1: Equal 0s and 1s

Language: L = {0ⁿ1ⁿ | n ≥ 0} = {ε, 01, 0011, 000111, ...}

Claim: L is not regular.

Proof:

Assume L is regular with pumping length p.

Choose w = 0^p 1^p (p zeros followed by p ones). Note |w| = 2p ≥ p, and w ∈ L.

By the Pumping Lemma, w = xyz where |y| ≥ 1 and |xy| ≤ p.

Since |xy| ≤ p, the string xy lies entirely within the first p characters of w. The first p characters of w are all 0s. Therefore:

• x = 0^a for some a ≥ 0
• y = 0^b for some b ≥ 1 (since |y| ≥ 1)
• z = 0^{p a b} 1^p

Now pump: let k = 0. Then xy⁰z = xz = 0^{p b} 1^p.

Since b ≥ 1, we have p − b < p. So xy⁰z has fewer 0s than 1s. Therefore xy⁰z ∉ L.

This contradicts condition 3 (pumping must stay in L). Therefore L is not regular. □

Classic Example 2: Self Repeating Strings

Language: L = {ww | w ∈ {0,1}*} = {ε, 00, 11, 0101, 1010, 001001, ...}

Claim: L is not regular.

Proof:

Assume L is regular with pumping length p.

Choose w = 0^p 1 0^p 1 (this is in L because it equals ww where w = 0^p 1).

|w| = 2p + 2 ≥ p. ✓

By the Pumping Lemma, w = xyz where |y| ≥ 1 and |xy| ≤ p.

Since |xy| ≤ p and the string starts with p zeros, xy lies entirely within the leading 0s:

• y = 0^b for some 1 ≤ b ≤ p

Pump with k = 2: xy²z = x(yy)z = 0^{p+b} 1 0^p 1.

For this to be in L = {ww}, it must equal some w'w' two equal halves. The total length is 2p + b + 2. Since b is odd or even, this length might be even or odd. But crucially:

The two halves must be equal, meaning the string must be symmetric around its midpoint. The midpoint of 0^{p+b} 1 0^p 1 splits the string asymmetrically because p+b ≠ p. Therefore xy²z ∉ L.

This contradicts condition 3. Therefore L is not regular. □

Classic Example 3: Prime Length Strings

Language: L = {1^n | n is prime}

Claim: L is not regular.

Proof:

Assume L is regular with pumping length p.

Let m be any prime with m ≥ p + 2. Choose w = 1^m ∈ L.

By the Pumping Lemma: w = xyz, |y| = b ≥ 1, |x| + |y| ≤ p, so |x| = a and |z| = m − a − b.

Consider pumping with k = m − b (where b = |y|): xy^{m b}z has length:

a + b(m-b) + (m-a-b)
= a + bm - b² + m - a - b
= bm - b² + m - b
= m(b+1) - b(b+1)
= (m-b)(b+1)

Since b ≥ 1 and m ≥ p + 2 > 2, we have b+1 ≥ 2 and m − b ≥ 2. Therefore (m−b)(b+1) is composite (a product of two factors, both ≥ 2). So xy^{m b}z ∉ L.

Contradiction. L is not regular. □

Common Mistakes in Pumping Lemma Proofs

What the Pumping Lemma Cannot Do

The Pumping Lemma is a necessary condition for regularity, not a sufficient one. There exist non regular languages that also satisfy the pumping lemma. If a language satisfies the pumping property, you cannot conclude it is regular only that you have not yet found a contradiction.

To prove a language regular, construct a DFA/NFA/regex for it. The Pumping Lemma is only useful for proving languages are NOT regular.

Languages at a Glance

The Takeaway

The Pumping Lemma is a test. Regular languages must pass it. Many languages fail it and that failure is your proof that no DFA, no NFA, no regex can ever recognize them.

The boundary between regular and non regular is the boundary between finite memory and infinite memory. A DFA can remember which state it is in but states are finite. Anything that requires counting without bound, anything that requires remembering the entire history of the input, anything that requires matching distant parts of the string none of these are regular.

In Lesson 8, you will see that closure properties give another powerful toolset for the same purpose sometimes making it possible to prove non regularity without invoking the Pumping Lemma at all.