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
- |xy| ≤ p (the loop is near the start),
- |y| ≥ 1 (the loop reads something),
- 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")Line by line
anbntests membership in aⁿbⁿ, andeven_lengthtests a language that is regular.surviving_splittries every split with |xy| ≤ p and |y| ≥ 1, and pumps y for k = 0, 1, 2 and 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.
- 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
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.