Chapter 16 of 34

Pumping Lemma for Regular Languages

On this page

So far we have built DFAs, NFAs and regular expressions for many languages. But some languages refuse to be captured, no matter how clever the design. Try building a DFA for "some a's followed by the same number of b's" and you will keep running out of states.

Failing to find a DFA is not a proof that none exists. Maybe we just were not clever enough. To prove that a language is not regular, we need a tool. The most famous one is the pumping lemma.

The pumping lemma for regular languages states that every sufficiently long string in a regular language contains a short, non-empty piece near the beginning that can be repeated any number of times (or removed), and the resulting strings stay in the language.

In this chapter we will understand why the lemma is true, state it precisely, learn the "game" view that makes proofs easy, and work through the standard exam problems step by step. We will also see what the lemma cannot do, which is a favourite GATE trap.


Why Some Languages Are Not Regular

A DFA has a fixed, finite number of states. That is its only memory. Whatever it needs to remember about the input read so far must fit into "which state am I in?"

Consider L = { anbn | n ≥ 0 }. After reading the a's, the machine must remember exactly how many a's it saw, so that it can check the b's. But n can be 1, 2, 1000, a million... Infinitely many different counts, finitely many states. Sooner or later two different counts must share a state, and then the machine cannot tell them apart.

The pumping lemma turns this "finite memory" argument into a reusable proof technique.


The Intuition: Long Strings Force a Loop

Take any DFA with p states. Feed it a string of length p or more. While reading the first p symbols, the DFA visits p + 1 states (the start state plus one state after each symbol). There are only p distinct states, so by the pigeonhole principle, some state must repeat.

A repeated state means the DFA walked around a loop. The part of the input read on that loop can be:

  • skipped (go around the loop 0 times),

  • repeated (go around 2, 3, 100 times),

and the DFA ends in exactly the same final state either way. So the modified strings are accepted too.

                 y
              +-----+
              |     |
              v     |
 start --x--> ( q ) -+ --z--> (( final ))

 w = x y z     the DFA is in state q after x, and again after x y
 x y^0 z = x z, x y^2 z = x y y z, ...  all end in the same final state

A concrete example

Let the DFA count a's modulo 3 over Σ = {a, b}. It has 3 states q0, q1, q2, start and final state q0, so it accepts strings whose number of a's is a multiple of 3.

State

a

b

→ * q0

q1

q0

q1

q2

q1

q2

q0

q2

Here p = 3. Take w = aaab (length 4 ≥ 3). The states visited are:

position :  0    1    2    3    4
read     :     a    a    a    b
state    :  q0   q1   q2   q0   q0
            ^              ^
            first repeat among the first p+1 = 4 states

State q0 repeats at positions 0 and 3. So x = ε, y = aaa, z = b. Pumping gives b, aaab, aaaaaab, ... Every one of them has a multiple of 3 a's, so every one is accepted. The loop is real.


The Pumping Lemma (Formal Statement)

If L is a regular language, then there exists an integer p ≥ 1 (the pumping length) such that every string w ∈ L with |w| ≥ p can be written as w = xyz, where:

1. |y| ≥ 1 (y is not empty),

2. |xy| ≤ p (the loop is found within the first p symbols),

3. for every i ≥ 0, x yi z ∈ L.

Here yi means y repeated i times, and y0 = ε.

Proof

Since L is regular, some DFA M with p states accepts it. Let w = w1w2…wn ∈ L with n ≥ p. Let r0 be the start state and rk the state after reading w1…wk.

  1. The p + 1 states r0, r1, …, rp are drawn from only p states, so rs = rt for some 0 ≤ s < t ≤ p.

  2. Put x = w1…ws, y = ws+1…wt, z = wt+1…wn.

  3. |y| = t − s ≥ 1 and |xy| = t ≤ p.

  4. Reading y takes M from rs back to rs (because rt = rs). So reading yi also takes rs to rs, for any i ≥ 0. After x yi the machine is in rs, and then z leads to rn, which is final. Hence x yi z ∈ L. ∎

Notice that p can be taken as the number of states of any DFA for L. (For a finite language, p = 1 + length of the longest string works, since then no string in L is long enough and the condition is vacuously true.)

Reading the quantifiers carefully

The lemma is a chain of "there exists" and "for all". Getting them right is the whole game.

Part of the statement

Quantifier

Who chooses it in a proof of non-regularity

pumping length p

there exists

opponent (you must handle any p)

string w ∈ L, |w| ≥ p

for every

you (pick one clever w)

split w = xyz with |xy| ≤ p, |y| ≥ 1

there exists

opponent (you must handle every legal split)

pumping count i ≥ 0

for every

you (pick one i that breaks it)


Using the Lemma: The Adversary Game

We use the lemma in its contrapositive form: if some long string in L cannot be pumped, then L is not regular. The proof is easiest to think of as a game against an opponent who claims L is regular.

  1. Assume L is regular. Let p be its pumping length (the opponent picks p; you treat it as an unknown number).

  2. You choose a string w ∈ L with |w| ≥ p. Write it in terms of p.

  3. The opponent splits w = xyz with |xy| ≤ p and |y| ≥ 1. You do not know the split, so you must consider all possible splits.

  4. You choose an i ≥ 0 such that x yi z ∉ L.

  5. This contradicts the lemma, so L is not regular.

The secret of easy proofs is step 2. Choose w so that the condition |xy| ≤ p pins y down. Usually that means w starts with a block of p identical symbols, so y is forced to lie inside that block. Then there is only one case to handle.


Solved Problems

Problem 1: L = { anbn | n ≥ 0 }

  1. Assume L is regular with pumping length p.

  2. Choose w = apbp. Clearly w ∈ L and |w| = 2p ≥ p.

  3. Any split has |xy| ≤ p, and the first p symbols of w are all a's. So x and y contain only a's. Say y = ak with 1 ≤ k ≤ p.

  4. Take i = 2: x y2 z = ap+kbp. Since k ≥ 1, the number of a's is more than the number of b's, so it is not in L.

  5. Contradiction. L is not regular. ∎

Problem 2: L = { w ∈ {0,1}* | w has equally many 0s and 1s }

Choose w = 0p1p ∈ L. As before, y = 0k with 1 ≤ k ≤ p. With i = 2 we get 0p+k1p, which has more 0s than 1s. Not in L, so L is not regular. ∎

Warning, a bad choice of w: if you choose w = (01)p, the opponent can pick x = ε, y = 01. Then x yi z = (01)p+i−1, which always has equal counts. That w can be pumped, so it proves nothing. The language is still non-regular; you just picked the wrong string. When one w fails, try another.

Problem 3: Palindromes over {a, b}

L = { w | w = wR }.

  1. Choose w = apbap. It reads the same backwards, so w ∈ L.

  2. y lies in the first block: y = ak, 1 ≤ k ≤ p.

  3. Take i = 0: x z = ap−kbap. Its reverse is apbap−k, which is a different string because the single b is no longer in the middle. So x z ∉ L.

  4. L is not regular. ∎

(Why not w = apap? Because a2p is a palindrome even after pumping. The b in the middle is what makes pumping visible.)

Problem 4: L = { an² | n ≥ 0 } (perfect-square lengths)

The language is over a single letter, so "where y is" does not matter; only its length k matters.

  1. Choose w = ap². Any split has y = ak with 1 ≤ k ≤ p (because |y| ≤ |xy| ≤ p).

  2. Take i = 2: |x y2 z| = p² + k.

  3. Now p² < p² + k ≤ p² + p < p² + 2p + 1 = (p + 1)².

  4. So p² + k lies strictly between two consecutive squares and is not a perfect square. x y2 z ∉ L. ∎

Problem 5: L = { aq | q is prime }

  1. Choose a prime q ≥ p + 2 (there are infinitely many primes) and w = aq. Let y = ak, 1 ≤ k ≤ p.

  2. Take i = q − k. Then |x yi z| = (q − k) + i·k = (q − k) + (q − k)k = (q − k)(1 + k).

  3. Both factors are at least 2: 1 + k ≥ 2 because k ≥ 1, and q − k ≥ 2 because q ≥ p + 2 and k ≤ p.

  4. A product of two numbers ≥ 2 is not prime, so x yi z ∉ L. ∎

This is the classic case where a "large" i is needed. i = 2 alone would not work for every k.

Problem 6: L = { anbm | n > m } (pumping down)

Pumping up (i = 2) only adds a's, which keeps n > m true. So we must pump down.

  1. Choose w = ap+1bp ∈ L (one more a than b).

  2. |xy| ≤ p, so y = ak with 1 ≤ k ≤ p.

  3. Take i = 0: x z = ap+1−kbp. Since k ≥ 1, the number of a's is p + 1 − k ≤ p, which is not greater than p. So x z ∉ L. ∎

Problem 7: L = { ww | w ∈ {a, b}* }

  1. Choose s = apb apb. It equals ww with w = apb, so s ∈ L.

  2. y = ak inside the first block of a's, 1 ≤ k ≤ p.

  3. Take i = 0: s' = ap−kb apb. Suppose s' = uu for some u. The last symbol of s' is b, so u ends in b. s' has exactly two b's, so each copy of u has exactly one b, at its end: u = ajb. Then uu = ajb ajb, which forces p − k = j = p, i.e. k = 0. That contradicts k ≥ 1. So s' ∉ L. ∎


A Shortcut: Closure Properties

Sometimes a pumping proof gets messy. A faster route uses the closure properties from the Closure Properties of Regular Languages chapter: regular languages are closed under intersection, complement, union, homomorphism, and so on.

Idea: if L were regular, then L ∩ R (R regular) would be regular too. If L ∩ R is a language we already know is non-regular, then L cannot be regular.

Example A: equal number of a's and b's

Let Leq = { w ∈ {a,b}* | #a(w) = #b(w) }. Then

L_eq ∩ a*b*  =  { a^n b^n | n ≥ 0 }

a*b* is regular. If Leq were regular, the intersection would be regular, but we proved anbn is not. So Leq is not regular.

Example B: L = { aibj | i ≠ j }

A direct pumping proof is awkward here (pumping can easily keep i ≠ j). Use complement instead:

(complement of L) ∩ a*b*  =  { a^n b^n | n ≥ 0 }

If L were regular, its complement would be regular, and so would this intersection. Contradiction. So L is not regular.


The Lemma Is Necessary, Not Sufficient

The pumping lemma says: regular ⇒ pumpable. It does not say: pumpable ⇒ regular.

So the lemma can only ever disprove regularity. You can never use it to prove that a language is regular. To prove regularity, build a DFA, NFA or regular expression, or use closure properties.

There really are non-regular languages that satisfy the pumping condition. A standard one:

F = { a^i b^j c^k  |  i, j, k ≥ 0, and if i = 1 then j = k }
  • F is pumpable with p = 2. Take any w ∈ F with |w| ≥ 2. If w has no a's, pump its first symbol (the string stays in b*c*, where any j, k are allowed). If i = 1, pump that single a: you get i = 0 or i ≥ 2, where any j, k are allowed. If i = 2, pump y = aa: i becomes 0, 2, 4, …, never 1. If i ≥ 3, pump one a: the number of a's becomes i − 1 + (extra copies) ≥ 2, never 1. In every case all pumped strings stay in F. (p = 1 is not enough: for w = aabcc the only allowed y is the first a, and pumping down gives abcc, which has i = 1 but j ≠ k.)

  • F is not regular. F ∩ ab*c* = { abncn | n ≥ 0 }, which is non-regular by the same argument as anbn.

(We also checked the pumping claim by a brute-force program for every string of F up to length 9.) The exact characterisation of regular languages is the Myhill–Nerode theorem from the DFA Minimization chapter: L is regular if and only if it has finitely many equivalence classes.

Minimum pumping length (a side note)

Some exams ask for the smallest p that works. Example: L = 0001*.

  • p = 3 fails: w = 000 ∈ L, and every way of pumping a piece of 000 up or down gives a string with the wrong number of 0s.

  • p = 4 works: every w ∈ L with |w| ≥ 4 is 0001k with k ≥ 1. Take x = 000, y = 1 (so |xy| = 4). Pumping gives 0001k−1+i ∈ L.

So the minimum pumping length of 0001* is 4. (Similarly, for a finite language it is one more than the longest string.)


Regular or Not? Classic Cases

Many GATE questions simply ask which languages are regular. The key question is always: does recognising it need unbounded memory?

Language

Regular?

Why

{ anbn | n ≥ 0 }

No

Problem 1

{ anbn | n ≤ 1000 }

Yes

Finite language; every finite language is regular

{ ambn | m, n ≥ 0 }

Yes

It is a*b*; m and n are independent

{ ambn | m + n is even }

Yes

Only parity of length matters

{ ambn | m ≡ n (mod 3) }

Yes

Track (m − n) mod 3: finitely many values

{ ww | w ∈ {a}* }

Yes

It is just (aa)*, even-length strings of a's

{ ww | w ∈ {a,b}* }

No

Problem 7

{ w | w = wR }

No

Problem 3

{ w x wR | w, x ∈ {a,b}+ }

Yes

Equals: length ≥ 3, first symbol = last symbol (take w as one symbol)

{ w | #ab(w) = #ba(w) } (count of substrings)

Yes

True exactly when w = ε or w starts and ends with the same symbol

{ w | #a(w) = #b(w) }

No

Closure Example A

{ an² }, { a2n }, { aprime }

No

Gaps between lengths grow without bound

{ anbm | n > m }

No

Problem 6

The two "surprisingly regular" rows (w x wR and #ab = #ba) were checked by a program on every string up to length 12.


Common Mistakes

  • Using the lemma to prove a language is regular. Impossible. Passing the pumping test proves nothing (see language F).

  • Choosing the split yourself. You do not get to pick x, y, z. You must show that every legal split fails. Choose w so that there is only one kind of split.

  • Forgetting |xy| ≤ p. Without it, y could be anywhere, and you would need many cases. This condition is your best friend.

  • Choosing a specific number for p, such as "let p = 3". p is unknown; your w must be written in terms of p.

  • Choosing a w that is not in L, or one shorter than p.

  • Only trying i = 2. Sometimes pumping up keeps the string in L and you need i = 0 (Problem 6) or a large i (Problem 5).

  • Thinking "looks like it needs counting" always means non-regular. { ambn | m ≡ n (mod 3) } and #ab = #ba both look like counting but are regular.


GATE and Interview Questions

Q1. What can the pumping lemma for regular languages be used for?

Only to prove that a language is not regular (by contradiction). It is a necessary condition for regularity, not a sufficient one.

Q2. Which of these are regular? (i) { anbn | 1 ≤ n ≤ 50 } (ii) { a2n | n ≥ 0 } (iii) { anb2n | n ≥ 0 } (iv) { an | n is a power of 2 }

(i) regular: finite. (ii) regular: it is (aa)*. (iii) not regular: choose apb2p, pump the a's with i = 2. (iv) not regular: with w = a2p and i = 2, the length becomes 2p + k with 1 ≤ k ≤ p < 2p, strictly between 2p and 2p+1.

Q3. In a pumping proof for { 0n1n }, a student picks w = 0p/21p/2. What is wrong?

(Assume p is even so that p/2 is a whole number.) Now |w| = p, but y may contain both 0s and 1s (for example y = 0p/21p/2), so there are several cases to handle. The proof is still possible (pumping a y that contains both symbols creates 1-before-0 order violations), but it is much messier. Choosing w = 0p1p forces y to be all 0s and gives a one-line proof.

Q4. Is the language { w x wR | w, x ∈ {a, b}+ } regular?

Yes. Any string of length ≥ 3 whose first and last symbols are equal is in the language: take w as that one symbol and x as the middle. Conversely, every string in the language starts and ends with the first symbol of w. So the language is a(a+b)+a + b(a+b)+b, which is regular.

Q5. If L is regular, a DFA for it has 7 states. Give a valid pumping length.

p = 7. Any string of length ≥ 7 makes the DFA visit 8 states among the first 7 symbols, so a state repeats. (Any larger p also works.)

Q6. L1 = { anbn } is non-regular. Is L1 ∪ { ambn | m ≠ n } regular?

Yes. The union is exactly a*b*, which is regular. A union of non-regular languages can be regular. Closure properties only work in one direction: "regular op regular is regular".

Q7. Why must y be non-empty in the lemma?

If y = ε were allowed, every language would trivially satisfy the lemma (pumping ε changes nothing), and the lemma would be useless. y is the input read on a real loop of at least one transition, so it is non-empty.


Summary

  • A DFA with p states must repeat a state while reading any p symbols. The input read on that loop, y, can be removed or repeated.

  • Pumping lemma: if L is regular, there is a p such that every w ∈ L with |w| ≥ p splits as xyz with |y| ≥ 1, |xy| ≤ p and x yi z ∈ L for all i ≥ 0.

  • Use it as a game: opponent picks p, you pick w, opponent picks the split, you pick i.

  • Choose w so that |xy| ≤ p forces y into one block of identical symbols.

  • Try i = 2, but remember i = 0 (pumping down) and large i (primes).

  • Closure properties (intersection with a regular language, complement) often give faster proofs.

  • The lemma is necessary but not sufficient. It can never prove that a language is regular.

Finite states mean finite memory. Pumping is how we catch a machine that would need to remember too much.