# Pumping Lemma Worked Proofs — A Proof Template, Five Solved Examples and the Context-Free Version

Source: https://skills101.in/learn/theory-of-computation/toc-pumping-lemma-worked-proofs — Skills101 free tutorial (Theory of Computation (TOC)). Updated 2026-11-21.

The [pumping lemma lesson](https://skills101.in/learn/theory-of-computation/pumping-lemma-dfa-minimisation) 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.

![The pumping lemma as a four-move game: the opponent picks the pumping length p, you pick a string s in L with length at least p, the opponent picks any split s = xyz with the length rules, and you pick a number i so that x y to the i z is not in L; if you can always win, L is not regular](https://skills101.in/learn-img/theory-of-computation/pumping-game.svg)

| 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:

1. Assume, for contradiction, that L is regular. Let p be its pumping length.
2. Choose s = … (in terms of p). Check that s ∈ L and |s| ≥ p.
3. Let s = xyz be any split with |xy| ≤ p and |y| ≥ 1.
4. Because |xy| ≤ p, describe what y **must** contain (usually: only the first kind of symbol, y = aᵏ with 1 ≤ k ≤ p).
5. Choose i and show xyⁱz ∉ L.
6. 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}

1. Assume L is regular with pumping length p.
2. Choose **s = 0ᵖ⁺¹1ᵖ**. It has one more 0 than 1s, so s ∈ L, and |s| = 2p + 1 ≥ p.
3. Let s = xyz with |xy| ≤ p and |y| ≥ 1.
4. The first p + 1 symbols are 0s, so y = 0ᵏ with 1 ≤ k ≤ p.
5. 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.
6. 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:

```python
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))
```

```text
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}

1. Assume L is regular with pumping length p.
2. Choose **s = a^(p²)**. Its length is a perfect square, so s ∈ L, and p² ≥ p.
3. Let s = xyz with |xy| ≤ p and |y| = k ≥ 1.
4. Here every symbol is `a`, so only the **length** matters: 1 ≤ k ≤ p.
5. 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.
6. Contradiction. ∎

```python
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))
```

```text
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. ∎

```python
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))
```

```text
['', '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:

1. **|vx| ≥ 1** (at least one of v, x is non-empty),
2. **|vwx| ≤ p** (the pumped part fits in a window of length p),
3. **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

1. Assume L is context-free with pumping length p.
2. Choose **s = aᵖbᵖcᵖ** ∈ L.
3. Let s = uvwxy be any split with |vwx| ≤ p and |vx| ≥ 1.
4. 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.
5. 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.
6. Contradiction. ∎

![Where the window vwx can sit in a to the p, b to the p, c to the p: inside the a's, across a and b, inside the b's, across b and c, or inside the c's; because the window is at most p long it never reaches from the a's to the c's, so pumping changes at most two of the three counts](https://skills101.in/learn-img/theory-of-computation/cfl-window-cases.svg)

Checking every split by hand is tedious; for small p a program can do it:

```python
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}")
```

```text
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 |s| ≥ p. |
| "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.


Practice quiz and free certificate: https://skills101.in/learn/theory-of-computation/toc-pumping-lemma-worked-proofs