Pumping Lemma for Regular Languages

Why we need it

A finite automaton has a fixed number of states, so it can’t count without limit. That suggests languages like aⁿbⁿ are not regular, but “I couldn’t build a DFA” is not a proof. The pumping lemma turns this intuition into a rigorous argument.

What the lemma says

If L is regular, there is a number p (the pumping length) such that every string s ∈ L with |s| ≥ p can be split into three parts, s = xyz, with:

1. |xy| ≤ p: y lies within the first p symbols,
2. |y| ≥ 1: y is not empty,
3. xyⁱz ∈ L for every i ≥ 0: y can be deleted (i = 0) or repeated (i = 2, 3, …) and the string stays in L.

Why it’s true: take a DFA for L with p states. While it reads the first p symbols of s it visits p + 1 states, so some state must repeat (the pigeonhole principle). The symbols read between the two visits form a loop, and that loop is y. The machine can go round it zero times or a hundred times and still end in the same state.

The proof as a game

To show L is not regular, assume it is and reach a contradiction. It helps to think of it as a game against an opponent who claims L is regular:

Step	Who chooses	What
1	opponent	the pumping length p (you don’t know it, so treat it as any number)
2	you	a string s ∈ L with |s| ≥ p
3	opponent	a split s = xyz with |xy| ≤ p and |y| ≥ 1 (you must handle every split)
4	you	a number i ≥ 0 so that xyⁱz ∉ L

If you can always win step 4, whatever the opponent did, L is not regular.

Example 1: aⁿbⁿ is not regular

• Choose s = aᵖbᵖ. It is in L and longer than p.
• Any split has |xy| ≤ p, so y is made only of a’s: y = aᵏ with k ≥ 1.
• Pump with i = 2: xy²z = aᵖ⁺ᵏbᵖ has more a’s than b’s, so it is not in L.
• This works for every split, which is a contradiction. aⁿbⁿ is not regular.

The model checks all 10 splits for p = 4 with Try every split.

Example 2: aⁱbʲ with i > j, pumping down

Choose s = aᵖ⁺¹bᵖ. Again y = aᵏ. Pumping up only adds a’s and keeps i > j, so it doesn’t help. Pump down instead: with i = 0, xz = aᵖ⁺¹⁻ᵏbᵖ has at most p a’s for p b’s, so it is not in L. Remember that i = 0 is allowed.

Example 3: palindromes

Choose s = aᵖbaᵖ. y = aᵏ sits in the left block of a’s, so pumping it to aᵖ⁺ᵏbaᵖ makes the two sides unequal, and the string is no longer a palindrome.

The contrast: a regular language

Run the same game on ab with the same s = aᵖbᵖ. Pumping a block of a’s always leaves “some a’s, then some b’s”, so some split survives every i and you can’t win. That is how it should be: ab is regular. But the lemma only works in one direction. Passing the test does not prove a language is regular. Some non-regular languages pass it too. To show a language is regular, build an automaton or a regular expression for it.

Choosing a good s

• Make s depend on p (like aᵖbᵖ), so it works for whatever p the opponent picked.
• Put the “hard part” at the start. Because |xy| ≤ p, you then know exactly what y can contain.
• Check that s really is in L and has at least p symbols.

Code

import re

def in_anbn(w):
    return re.fullmatch('a*b*', w) is not None and w.count('a') == w.count('b')

def splits(s, p):
    """Every split s = xyz with |xy| <= p and |y| >= 1."""
    for xl in range(p):
        for yl in range(1, p - xl + 1):
            yield s[:xl], s[xl:xl + yl], s[xl + yl:]

def breaks_every_split(s, p, in_lang, tries=(0, 2, 3)):
    for x, y, z in splits(s, p):
        if all(in_lang(x + y * i + z) for i in tries):
            return False, (x, y, z)        # this split survives: no contradiction
    return True, None

p = 4
s = 'a' * p + 'b' * p                      # aaaabbbb
print(breaks_every_split(s, p, in_anbn))   # (True, None): a^n b^n is not regular
print(breaks_every_split(s, p, lambda w: re.fullmatch('a*b*', w) is not None))
# (False, ('', 'a', 'aaabbbb')): a*b* is regular, so some split always survives

A program can only try one p and a few values of i. A real proof argues for every p at once, as in the examples above.

Common mistakes

• Choosing the split yourself. The opponent chooses it, so the proof must cover every split allowed by |xy| ≤ p and |y| ≥ 1.
• Using a specific p, like “let p = 3”. p is unknown, so the argument must work for any p.
• Trying to prove a language is regular with the lemma. It can only prove the opposite.
• Picking s outside L, or shorter than p. Then the lemma promises nothing.
• Forgetting i = 0. Sometimes only pumping down breaks the string.