AdvancedTheory of Computation (TOC) · Lesson 10 of 14 · Updated ·
Pumping Lemma Worked Proofs — A Proof Template, Five Solved Examples and the Context-Free Version
The pumping lemma lesson explained why the lemma is true and proved that aⁿbⁿ is not regular. Students usually understand the idea and still lose marks in the exam, because the proof has a strict logical shape. This lesson gives you that shape as a template, then uses it on five different languages. For each proof, a short Python program checks the key step — that every allowed split fails — for small values of p.
1. The proof is a game
The pumping lemma statement has four "for all / there exists" parts. The easiest way to get them right is to see a proof as a game against an opponent who wants the language to look regular.
| Move | Who | What | Your job in the proof |
|---|---|---|---|
| 1 | opponent | the pumping length p | treat p as unknown; never give it a value |
| 2 | you | a string s ∈ L with |s| ≥ p | choose s in terms of p, cleverly |
| 3 | opponent | any split s = xyz with |xy| ≤ p and |y| ≥ 1 | handle every possible split |
| 4 | you | a number i ≥ 0 | show xyⁱz ∉ L |
If you can win for every p and every split, the language is not regular.
2. The template
Write every proof in these six lines:
- Assume, for contradiction, that L is regular. Let p be its pumping length.
- Choose s = … (in terms of p). Check that s ∈ L and |s| ≥ p.
- Let s = xyz be any split with |xy| ≤ p and |y| ≥ 1.
- Because |xy| ≤ p, describe what y must contain (usually: only the first kind of symbol, y = aᵏ with 1 ≤ k ≤ p).
- Choose i and show xyⁱz ∉ L.
- This contradicts the pumping lemma, so L is not regular. ∎
Step 4 is where most marks are won. Choosing s so that the first p symbols are all the same letter makes step 4 a one-liner.
3. Proof 1 — pumping down: L = {0ⁿ1ᵐ | n > m}
- Assume L is regular with pumping length p.
- Choose s = 0ᵖ⁺¹1ᵖ. It has one more 0 than 1s, so s ∈ L, and |s| = 2p + 1 ≥ p.
- Let s = xyz with |xy| ≤ p and |y| ≥ 1.
- The first p + 1 symbols are 0s, so y = 0ᵏ with 1 ≤ k ≤ p.
- Take i = 0: xz = 0ᵖ⁺¹⁻ᵏ1ᵖ. Now the number of 0s is p + 1 − k ≤ p, which is not more than the number of 1s. So xz ∉ L.
- Contradiction. ∎
Pumping up (i = 2) does not work here: adding 0s keeps n > m. You must pick the i that breaks the language. The program below tries i = 0, 1, 2, 3 on every split and reports the first i that breaks it:
def splits(s, p):
for xy_len in range(1, p + 1):
for y_len in range(1, xy_len + 1):
yield s[:xy_len - y_len], s[xy_len - y_len:xy_len], s[xy_len:]
def winning_i(s, p, in_lang, tries=range(4)):
result = {}
for x, y, z in splits(s, p):
i = next((i for i in tries if not in_lang(x + y * i + z)), None)
result[i] = result.get(i, 0) + 1
return result # {i that breaks the split: how many splits}
def more_zeros(w):
n = len(w) - len(w.lstrip("0"))
return w == "0" * n + "1" * (len(w) - n) and n > len(w) - n
for p in [3, 5, 7]:
s = "0" * (p + 1) + "1" * p
print(f"p={p}: splits broken by each i ->", winning_i(s, p, more_zeros))
p=3: splits broken by each i -> {0: 6}
p=5: splits broken by each i -> {0: 15}
p=7: splits broken by each i -> {0: 28}
Every split is broken by i = 0, and no split survives (there is no None key). Try changing tries to range(1, 4) and the result becomes {None: …} for every split: pumping up only adds 0s, so the string stays in L.
4. Proof 2 — lengths that are perfect squares: L = {a^(n²) | n ≥ 0}
- Assume L is regular with pumping length p.
- Choose s = a^(p²). Its length is a perfect square, so s ∈ L, and p² ≥ p.
- Let s = xyz with |xy| ≤ p and |y| = k ≥ 1.
- Here every symbol is
a, so only the length matters: 1 ≤ k ≤ p. - Take i = 2: |xy²z| = p² + k. Since 1 ≤ k ≤ p, p² < p² + k ≤ p² + p < p² + 2p + 1 = (p + 1)². The length lies strictly between two consecutive squares, so it is not a square, and xy²z ∉ L.
- Contradiction. ∎
import math
def is_square_length(w):
r = math.isqrt(len(w))
return set(w) <= {"a"} and r * r == len(w)
for p in [2, 4, 6, 9]:
s = "a" * (p * p)
lengths = sorted({p * p + k for k in range(1, p + 1)})
print(f"p={p}: pumped lengths {lengths[0]}..{lengths[-1]}, next square {(p + 1) ** 2}, any square:",
any(is_square_length("a" * n) for n in lengths))
p=2: pumped lengths 5..6, next square 9, any square: False
p=4: pumped lengths 17..20, next square 25, any square: False
p=6: pumped lengths 37..42, next square 49, any square: False
p=9: pumped lengths 82..90, next square 100, any square: False
The same "gap" argument proves {aⁿ | n is prime} and {a^(2ⁿ)} are not regular: the gaps between primes (or powers of 2) eventually become larger than any pumped amount.
5. Proof 3 — use closure properties instead: L = {aⁱbʲ | i ≠ j}
Pumping this language directly is awkward: pumping usually turns one inequality into another inequality. There is a cleaner route.
- Regular languages are closed under complement and intersection.
- If L were regular, then L′ (its complement) would be regular, and so would L′ ∩ a*b*.
- But L′ ∩ a*b* is the set of strings of the form aⁱbʲ with i = j, which is exactly {aⁿbⁿ} — and we know that is not regular.
- Contradiction, so L is not regular. ∎
import re
from itertools import product
L = lambda w: re.fullmatch(r"a*b*", w) is not None and w.count("a") != w.count("b")
strings = ["".join(t) for n in range(9) for t in product("ab", repeat=n)]
result = [w for w in strings if not L(w) and re.fullmatch(r"a*b*", w)]
print(result)
print("is exactly a^n b^n:", all(w == "a" * (len(w) // 2) + "b" * (len(w) // 2) for w in result))
['', 'ab', 'aabb', 'aaabbb', 'aaaabbbb']
is exactly a^n b^n: True
Tip: whenever a language looks like "a known non-regular language with something added", try closure properties first: intersection with a regular language, complement, or a substitution.
6. The pumping lemma for context-free languages
For context-free languages, the lemma pumps two pieces at once:
If L is context-free, there is a p such that every s ∈ L with |s| ≥ p can be split s = uvwxy with:
- |vx| ≥ 1 (at least one of v, x is non-empty),
- |vwx| ≤ p (the pumped part fits in a window of length p),
- uvⁱwxⁱy ∈ L for every i ≥ 0.
The game is the same: the opponent picks p and the split; you pick s and i.
Proof 4 — L = {aⁿbⁿcⁿ | n ≥ 0} is not context-free
- Assume L is context-free with pumping length p.
- Choose s = aᵖbᵖcᵖ ∈ L.
- Let s = uvwxy be any split with |vwx| ≤ p and |vx| ≥ 1.
- The window vwx has length at most p, so it cannot touch both the a's and the c's (there are p b's between them). So vx contains at most two of the three letters.
- Take i = 2. At least one letter's count goes up, and at least one letter's count stays at p. The three counts are no longer equal (or the letters fall out of order), so uv²wx²y ∉ L.
- Contradiction. ∎
Checking every split by hand is tedious; for small p a program can do it:
def cfl_splits(s, p):
n = len(s)
for start in range(n):
for wlen in range(1, p + 1): # window vwx = s[start:start+wlen]
if start + wlen > n:
break
for vlen in range(wlen + 1):
for xlen in range(wlen - vlen + 1):
if vlen + xlen == 0:
continue
u, v = s[:start], s[start:start + vlen]
w = s[start + vlen:start + wlen - xlen]
x, y = s[start + wlen - xlen:start + wlen], s[start + wlen:]
yield u, v, w, x, y
def abc(t):
n = len(t) // 3
return t == "a" * n + "b" * n + "c" * n
for p in [2, 3, 4]:
s = "a" * p + "b" * p + "c" * p
total = survivors = 0
for u, v, w, x, y in cfl_splits(s, p):
total += 1
if all(abc(u + v * i + w + x * i + y) for i in (0, 2)):
survivors += 1
print(f"p={p}: {total} legal splits, splits surviving i=0 and i=2: {survivors}")
p=2: 37 legal splits, splits surviving i=0 and i=2: 0
p=3: 121 legal splits, splits surviving i=0 and i=2: 0
p=4: 295 legal splits, splits surviving i=0 and i=2: 0
No split survives, exactly as the proof says.
Proof 5 — L = {ww | w ∈ {a, b}*} is not context-free
The string a^p b^p is too easy for the opponent here; choose s = aᵖbᵖaᵖbᵖ (w = aᵖbᵖ).
- If vwx lies entirely in the first half, pump up with i = 2. The string grows by k = |vx| symbols, where 1 ≤ k ≤ p. If k is odd the length is odd, so it cannot be ww. If k is even, the middle of the new string moves k/2 ≤ p/2 places into what was the first half, so the second half now starts with b (from the first block of b's) while the first half starts with a. Not of the form ww. The case where vwx lies in the second half is symmetric: the first half now ends with a instead of b.
- If vwx straddles the middle, it lies inside the central bᵖaᵖ. Pumping down (i = 0) gives aᵖbʲaᵏbᵖ with j < p or k < p, which is not of the form ww.
In every case some i breaks it, so {ww} is not context-free. (By contrast, {wwᴿ}, a word followed by its reverse, is context-free — a PDA pushes the first half and pops while matching the second.)
7. Proofs that lose marks
| Wrong move | Why it fails |
|---|---|
| "Let p = 3." | p is chosen by the opponent; your proof must work for every p. |
| "Let x = a, y = a, z = …" | You must handle every split, not one convenient split. |
| Choosing s = (ab)ᵖ for aⁿbⁿ | It is not in the language. Always check s ∈ L. |
| Choosing a string shorter than p | The lemma only promises splits for |
| "The split works, so L is regular." | The lemma is one-way. It can only prove non-regularity. |
| Forgetting |xy| ≤ p | Without it you cannot say where y is, and the proof falls apart. |
Common mistakes
- Picking i = 2 out of habit when only i = 0 breaks the language (Proof 1).
- Using the regular pumping lemma for a context-free question, or the other way round.
- In the CFL lemma, assuming v and x are both non-empty. Only |vx| ≥ 1 is guaranteed.
- Forgetting the "window" argument (|vwx| ≤ p) in aⁿbⁿcⁿ, which is the key step.
- Not trying a closure-property argument when the direct proof gets messy.
Quick recap
- The lemma is a game: the opponent picks p and the split; you pick s ∈ L (|s| ≥ p) and i.
- Template: assume regular → choose s → any split with |xy| ≤ p, |y| ≥ 1 → locate y → choose i → contradiction.
- Pump down (i = 0) when pumping up stays in L; use length gaps for squares, primes and powers of 2.
- Closure shortcut: if L ∩ R or L′ ∩ R is a known non-regular language, L is not regular.
- CFL lemma: s = uvwxy, |vwx| ≤ p, |vx| ≥ 1; the short window proves aⁿbⁿcⁿ and ww are not context-free.