Beyond regular: the pumping lemma

Advanced

Introduction

Finite automata are powerful, but their memory is fixed. Can a DFA recognise aⁿbⁿ, the strings of some a's followed by the same number of b's? Intuitively no: it would have to remember how many a's it read, and the count can be larger than any fixed number of states. The pumping lemma turns this intuition into a proof, and it is the standard tool for showing that a language is not regular.

How it works

Suppose a DFA with p states reads a word w with at least p symbols. It visits p + 1 states in its first p moves, so by the pigeonhole principle some state repeats. The symbols read between the two visits form a loop. The machine can go round that loop any number of times, or skip it, and still end in the same place.

That gives the pumping lemma: if L is regular, there is a number p (the pumping length) such that every word w in L with |w| ≥ p can be split as w = xyz where

  1. |xy| ≤ p (the loop is near the start),
  2. |y| ≥ 1 (the loop reads something),
  3. xyᵏz is in L for every k ≥ 0.

To prove a language is not regular, argue by contradiction: assume it is, take the p from the lemma, and choose one word w in L with |w| ≥ p such that every allowed split fails for some k.

aⁿbⁿ is not regular. Choose w = aᵖbᵖ. Because |xy| ≤ p, both x and y lie inside the a's, so y = aʲ with j ≥ 1. Pumping down (k = 0) gives aᵖ⁻ʲbᵖ, which has fewer a's than b's and is not in L. Every split fails, so no DFA can recognise aⁿbⁿ.

The lemma is a one-way test. Every regular language passes it, but passing it does not prove a language is regular. To prove regularity, build an automaton or an expression.

In Python we cannot check "every k", but we can try every split of a given word for small k and see which ones survive.

Syntax

for i in range(p):                     # x = w[:i]
    for j in range(i + 1, p + 1):      # y = w[i:j], so |xy| = j <= p and |y| >= 1
        x, y, z = w[:i], w[i:j], w[j:]
        survives = all(language(x + y * k + z) for k in range(4))

Example

def anbn(w):
    n = len(w) // 2
    return w == "a" * n + "b" * n


def even_length(w):
    return len(w) % 2 == 0


def surviving_split(language, w, p, ks=range(4)):
    for i in range(p):
        for j in range(i + 1, p + 1):
            x, y, z = w[:i], w[i:j], w[j:]
            if all(language(x + y * k + z) for k in ks):
                return x, y, z
    return None


p = 4
for name, language, w in [("aⁿbⁿ", anbn, "aaaabbbb"), ("even length", even_length, "abab")]:
    split = surviving_split(language, w, p)
    if split:
        x, y, z = split
        print(f"{name}: w={w} pumps with x={x or 'ε'} y={y} z={z or 'ε'}")
    else:
        print(f"{name}: w={w} has no split that survives pumping")
Open in compiler

Line by line

  1. anbn tests membership in aⁿbⁿ, and even_length tests a language that is regular.
  2. surviving_split tries every split with |xy| ≤ p and |y| ≥ 1, and pumps y for k = 0, 1, 2 and 3.
  3. For aaaabbbb with p = 4, every y is made of a's only, so pumping changes the number of a's and no split survives.
  4. For abab, the split x = ε, y = ab, z = ab survives, because repeating ab keeps the length even.

Expected result

aⁿbⁿ: w=aaaabbbb has no split that survives pumping
even length: w=abab pumps with x=ε y=ab z=ab

In the real world

The pumping lemma explains why balanced brackets, matching HTML tags and correctly nested code blocks cannot be checked with regular expressions alone, and why parsers use stacks. It also explains why tools that try to "parse HTML with regex" break on nested input. Knowing that a problem is not regular tells you which kind of tool you need.

Common mistakes

  • Choosing the split yourself: the proof must work for every split the lemma allows.
  • Choosing a short word: w must have length at least p.
  • Using the lemma to prove a language regular: it can only prove non-regularity.
  • Forgetting k = 0: pumping down is often the easiest way to leave the language.

Best practices

  • Choose w so that |xy| ≤ p forces y into one simple region, such as the first block of a's.
  • Write the proof as a contradiction, step by step: assume, choose w, consider any split, pump, contradict.
  • Test your intuition in code on small p before writing the proof.

Summary

A DFA with p states repeats a state within any p symbols, so in a regular language every word of length at least p has a part y near its start that can be repeated or removed. To prove a language is not regular, pick a word for which every allowed split fails. aⁿbⁿ fails because pumping changes only the a's. Languages that need unbounded counting are not regular.

Quick check

1. In the pumping lemma, which condition keeps y near the start of w?
2. To prove L is not regular with the lemma, you must show that…
3. For w = aᵖbᵖ, why must y contain only a's?
4. A language passes the pumping lemma. What follows?

Key takeaways

  • A DFA with p states must repeat a state on any word of length p, so part of the word can be repeated.
  • To show L is not regular, find for every p a word that no split can pump.
  • Languages that need unbounded counting, such as aⁿbⁿ, are not regular.

Practice problems for this lesson

My notes

Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.