Skip to content
Tutorials Center
My learning

Topics

Lesson 16 of 59 Ā· Regular Expressions and Languages

The Pumping Lemma for Regular Languages

Learn the pumping lemma for regular languages, why it holds, and how to prove that a^n b^n, prime-length strings and other languages are not regular, with code.

Some languages simply cannot be recognized by a finite automaton: the language {a^n b^n} needs an unbounded counter. But "I could not find a DFA" is not a proof. The pumping lemma is the standard tool for proving rigorously that a language is not regular. It captures a consequence of having finitely many states: long strings must repeat a state, and the repeated part can be "pumped".

Why long strings can be pumped

Suppose a DFA has p states and accepts a string w with |w| ≄ p. While reading w, the machine visits at least p + 1 states (the start state plus one per symbol), so by the pigeonhole principle some state is visited twice. Everything between the two visits is a loop. The machine could go around that loop zero times, once (as before), twice, or any number of times and still end in the same final state. So pumping the loop's text up or down keeps the string in the language.

flowchart LR
    q0(("start")) -->|"x"| r(("r"))
    r -->|"y (loop)"| r
    r -->|"z"| f((("accept")))

The string w = xyz: x leads to the repeated state r, y is the loop, z finishes. Repeating y any number of times, including zero, still reaches the accepting state.

The statement

Pumping lemma. If L is a regular language, then there is a number p ≄ 1 (the pumping length) such that every string w in L with |w| ≄ p can be split into three parts w = xyz satisfying:

  1. |y| ≄ 1 (the loop is not empty),
  2. |xy| ≤ p (the loop appears within the first p symbols),
  3. x y^i z ∈ L for every i ≄ 0 (pumping up, i ≄ 2, or down, i = 0, stays in L).

In the proof, p can be the number of states of a DFA for L. The loop is found among the first p + 1 states visited, which gives condition 2.

It is a one-way test

The pumping lemma states: regular ⇒ pumpable. Logically, that only lets you prove non-regularity (if a language is not pumpable, it is not regular). It cannot prove that a language is regular: there are non-regular languages that satisfy the pumping conditions anyway. To show a language is regular, build an automaton or an expression instead.

Proving non-regularity: the adversary game

Think of a game between you (who want to prove L is not regular) and an adversary (who claims L is regular).

  1. The adversary picks the pumping length p.
  2. You pick a string w in L with |w| ≄ p. (Choose it cleverly, in terms of p.)
  3. The adversary splits w = xyz with |xy| ≤ p and |y| ≄ 1.
  4. You pick an i such that x y^i z is not in L.

If you can win for every p and every split, L is not regular.

Example: L = {a^n b^n : n ≄ 0}

Choose w = a^p b^p. Since |xy| ≤ p, both x and y lie inside the leading block of a's. So y = a^k with k ≄ 1. Pump with i = 2: x y² z = a^(p+k) b^p, which has more a's than b's, so it is not in L. Every split loses, so L is not regular.

The code below plays the adversary's side exhaustively for several values of p: it tries every legal split of w = a^p b^p and confirms that pumping always breaks the string.

Python Play the pumping game against a^n b^n

Press Run (or Ctrl + Enter) to see the result here.

Program input Ā· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For every p tried, all splits fail, which matches the written proof. The final lines show a concrete split: i = 1 gives the original string, but i = 0 and i = 2 break the balance between a's and b's.

More examples

Primes: L = {a^p : p is prime}. Take w = a^q for a prime q ≄ pumping length. Write y = a^k, k ≄ 1. Pump with i = q + 1: the string x y^(q+1) z has length q + kq = q(1 + k), which is a product of two numbers greater than 1, so it is not prime. L is not regular.

Perfect squares: L = {a^(n²)}. Take w = a^(p²). Pumping once more adds between 1 and p symbols, giving a length strictly between p² and (p+1)² = p² + 2p + 1, so not a perfect square. Not regular.

Equal a's and b's: L = {w : #a(w) = #b(w)}. Same trick as a^n b^n, with w = a^p b^p. (Or use intersection with a*b* and the closure properties.)

Copies: L = {ww : w ∈ {a, b}*}. Take w = a^p b a^p b. The loop y lies in the first block of a's, and pumping changes the first half only, breaking the pattern.

Python Pumping the prime-length language

Press Run (or Ctrl + Enter) to see the result here.

Program input Ā· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Every prime p is broken, because for a suitable i the pumped length becomes composite, exactly as in the proof: 7 + 3Ā·7 = 28 = 7 Ɨ 4.

Pitfalls in pumping proofs

  • You cannot choose p or the split. The adversary does. Your proof must work for all p and all legal splits, so reason about "y is a block of a's of unknown length k ≄ 1", not a specific split.
  • Choose w using p. A fixed string like aabb cannot be pumped for any p larger than its length, because the lemma needs |w| ≄ p.
  • Use the |xy| ≤ p condition. It is what pins y inside the first block of symbols.
  • Do not use the lemma backwards. Passing the pumping test does not prove regularity.
  • Pump down too. i = 0 is sometimes the choice that breaks the string, such as in {a^n b^m : n > m}.

When the lemma is awkward, the Myhill-Nerode theorem gives an exact criterion: a language is regular iff it has finitely many classes of indistinguishable prefixes. Closure properties are another route, as seen in the previous lesson. The same pumping idea, with two pumped parts instead of one, works for context-free languages (see the pumping lemma for CFLs).

Check your understanding

Quick check Ā· 5 questions

of 5 answered You scored / 5 Ā· perfect!

  1. 1. What does the pumping lemma let you prove?

    The lemma says regular languages are pumpable. If a language is not pumpable, it cannot be regular. It cannot prove regularity.
  2. 2. In the proof for {a^n b^n}, why does y consist only of a's?

    The condition |xy| ≤ p confines y to the first p symbols, which are all a's in w = a^p b^p.
  3. 3. Which of these choices is made by YOU in a pumping-lemma proof?

    The adversary picks p and the split. You pick w (as a function of p) and the exponent i.
  4. 4. Why is pigeonhole used in the proof of the lemma?

    The repeated state creates a loop in the computation, and that loop's text is the pumpable part y.
  5. 5. Which language is NOT regular?

    The gaps between consecutive squares keep growing, so pumping a loop of bounded size cannot always land on another square.

Summary

  • Long strings in a regular language force a repeated DFA state, producing a loop that can be pumped: w = xyz with |y| ≄ 1, |xy| ≤ p and x y^i z ∈ L for all i ≄ 0.
  • The lemma proves non-regularity only; it cannot prove that a language is regular.
  • Proof as a game: the adversary picks p and the split; you pick w and i. Always argue about all legal splits.
  • Standard non-regular examples: a^n b^n, prime lengths, perfect squares, equal numbers of a's and b's, ww.
  • Closure properties and Myhill-Nerode are alternative tools.

Next: Context-Free Grammars