Limits of regular languages: pumping and Myhill–Nerode

Finite automata have finite memory, so some languages must be beyond them. The language \(\{a^n b^n : n \ge 0\}\) is the standard example: to check that the number of bs matches the number of as, a machine seems to need to count the as, and the count is unbounded. But 'seems to need' is not a proof. Perhaps some clever automaton avoids counting. This lesson gives two rigorous tools for proving that a language is not regular. The pumping lemma is a necessary condition every regular language satisfies; showing that a language violates it proves non-regularity. The Myhill–Nerode theorem is a complete characterization: it says exactly which languages are regular and, for those that are, how many states their smallest DFA has.

The pumping lemma

Pumping lemma for regular languages. If L is regular, there is a number p (the pumping length) such that every string \(s \in L\) with \(|s| \ge p\) can be written \(s = xyz\) with three properties: \(|y| \ge 1\), \(|xy| \le p\), and \(xy^iz \in L\) for every \(i \ge 0\). In words: every long enough string in L contains, near its start, a non-empty piece that can be repeated any number of times, or deleted, without leaving L.

The proof is the pigeonhole principle. Let M be a DFA for L with p states. Run M on a string s of length at least p. Reading the first p symbols visits \(p + 1\) states, counting the start state, so some state q appears twice among them. Let x be the part of s read before the first visit to q, y the part read between the two visits, and z the rest. Then \(|y| \ge 1\) because the visits are at different times, and \(|xy| \le p\) because both visits occur within the first p symbols. Reading y takes M from q back to q, so the loop can be traversed any number of times, including zero, and M ends in the same state as on s. Since s is accepted, so is every \(xy^iz\).

Using the pumping lemma

The lemma is used in the contrapositive: if for every candidate p some long string in L cannot be pumped, then L is not regular. The quantifiers matter, and it helps to think of the argument as a game against an adversary who claims L is regular. The adversary picks p. You pick a string \(s \in L\) with \(|s| \ge p\). The adversary splits s into xyz respecting \(|y| \ge 1\) and \(|xy| \le p\). You pick \(i \ge 0\). You win if \(xy^iz \notin L\). If you have a winning strategy, choosing s depending on p and i depending on the split, then L is not regular. You do not get to choose p or the split; you must win against every choice the adversary makes.

For \(L = \{a^n b^n\}\): given p, choose \(s = a^p b^p\), which is in L and long enough. Any split with \(|xy| \le p\) puts x and y entirely inside the block of as, so \(y = a^k\) with \(k \ge 1\). Choose \(i = 2\). Then \(xy^2z = a^{p+k}b^p\), which has more as than bs and is not in L. So no p works, and L is not regular. The program below plays this game exhaustively for small p, trying every legal split and finding a winning i each time. It cannot prove the theorem for all p, but it shows the structure of the argument and catches mistakes in the choice of s.

# The pumping game for L = { a^n b^n : n >= 0 }.
# For each candidate pumping length p, we choose s = a^p b^p. The adversary may split
# s = xyz with |xy| <= p and |y| >= 1. We show every split fails for some i.
def in_L(w):
    n = len(w) // 2
    return w == "a" * n + "b" * n

for p in range(1, 8):
    s = "a" * p + "b" * p
    splits, beaten = 0, 0
    for xy_len in range(1, p + 1):
        for y_len in range(1, xy_len + 1):
            x, y, z = s[:xy_len - y_len], s[xy_len - y_len:xy_len], s[xy_len:]
            splits += 1
            # find the smallest i in {0, 2, 3} with x y^i z outside L
            witness = next((i for i in (0, 2, 3) if not in_L(x + y * i + z)), None)
            beaten += witness is not None
    print(f"p = {p}: s = a^{p}b^{p}, {splits:2d} legal splits, all beaten: {beaten == splits}")
# an example split, shown in full
s = "aaaabbbb"
x, y, z = s[:1], s[1:3], s[3:]
print("example: x =", repr(x), " y =", repr(y), " z =", repr(z))
for i in range(4):
    w = x + y * i + z
    print(f"  i = {i}: {w:14s} in L? {in_L(w)}")

p = 1: s = a^1b^1,  1 legal splits, all beaten: True
p = 2: s = a^2b^2,  3 legal splits, all beaten: True
p = 3: s = a^3b^3,  6 legal splits, all beaten: True
p = 4: s = a^4b^4, 10 legal splits, all beaten: True
p = 5: s = a^5b^5, 15 legal splits, all beaten: True
p = 6: s = a^6b^6, 21 legal splits, all beaten: True
p = 7: s = a^7b^7, 28 legal splits, all beaten: True
example: x = 'a'  y = 'aa'  z = 'abbbb'
  i = 0: aabbbb         in L? False
  i = 1: aaaabbbb       in L? True
  i = 2: aaaaaabbbb     in L? False
  i = 3: aaaaaaaabbbb   in L? False

Choosing s well is the art. The constraint \(|xy| \le p\) is your friend: pick s so that its first p symbols are all the same, which pins down what y can be. For the language of palindromes over \(\{a, b\}\), choose \(s = a^p b a^p\); y lies in the first block of as, and pumping up breaks the symmetry. For \(\{ww : w \in \{a,b\}^*\}\), choose \(s = a^p b a^p b\). For \(\{a^{n^2}\}\) over a single letter, the as are all alike, so use lengths: pumping changes the length by \(|y| \le p\), and \(p^2 + |y|\) lies strictly between \(p^2\) and \((p+1)^2 = p^2 + 2p + 1\), so it is not a perfect square. For \(\{a^q : q \text{ prime}\}\), pick a prime \(q \ge p + 2\) and pump with \(i = q - |y|\), giving length \(q(1 + |y|)\), a product of two factors greater than 1.

The pumping lemma has limits. It is a necessary condition only: some non-regular languages can be pumped. A classic example is \(\{a^i b^j c^k : i = 0 \text{ or } j = k\}\), in which every long string can be pumped, yet the language is not regular. When pumping fails to help, two other tools work. Closure properties: if L were regular, then \(L \cap R\) would be regular for any regular R, and choosing R cleverly may produce a language known not to be regular. For example, the language of binary strings with equal numbers of 0s and 1s, intersected with \(0^*1^*\), gives \(\{0^n1^n\}\), so it cannot be regular. And the Myhill–Nerode theorem, which never fails.

The Myhill–Nerode theorem

Call strings x and y distinguishable by L if there is a string z such that exactly one of xz and yz is in L; otherwise they are indistinguishable, written \(x \equiv_L y\). Indistinguishability is an equivalence relation on \(\Sigma^*\), and its classes group prefixes that 'behave the same' with respect to every possible continuation. Theorem (Myhill and Nerode, 1957–58). L is regular if and only if \(\equiv_L\) has finitely many equivalence classes. Moreover, the number of classes equals the number of states of the smallest DFA for L, and that minimal DFA is unique up to renaming its states.

One direction generalizes the lower-bound argument from lesson 2. If a DFA for L has k states and \(\equiv_L\) had more than k classes, two strings from different classes would lead to the same state, and then every extension would give them the same answer, contradicting distinguishability. So the number of classes is at most the number of states of any DFA. The other direction builds a DFA directly from the classes: its states are the classes \([x]\), the start state is \([\varepsilon]\), the transition from \([x]\) on a goes to \([xa]\), and \([x]\) is accepting when \(x \in L\). These definitions do not depend on which representative x is chosen, because indistinguishable strings stay indistinguishable after appending a. This DFA has exactly as many states as there are classes, so it is minimal.

To prove a language non-regular with Myhill–Nerode, exhibit an infinite set of pairwise distinguishable strings. For \(\{a^n b^n\}\), the strings \(a^0, a^1, a^2, \ldots\) work: \(a^i\) and \(a^j\) with \(i \ne j\) are distinguished by \(z = b^i\), since \(a^ib^i \in L\) but \(a^jb^i \notin L\). This proof is often shorter and more transparent than the pumping argument, and it never fails, because a non-regular language always has infinitely many classes. The program below estimates the classes by brute force, comparing prefixes on all short suffixes. For three regular languages the count settles at the size of the minimal DFA; for \(a^nb^n\) it keeps growing as longer prefixes are allowed.

# Myhill-Nerode by brute force: group strings into classes that no short suffix distinguishes.
# For a regular language the number of classes is finite and equals the minimal DFA size.
from itertools import product

def strings(max_len, sigma="ab"):
    for n in range(max_len + 1):
        for t in product(sigma, repeat=n):
            yield "".join(t)

def classes(member, prefix_len=5, suffix_len=6):
    suffixes = list(strings(suffix_len))
    sig = {}
    for x in strings(prefix_len):
        key = tuple(member(x + z) for z in suffixes)
        sig.setdefault(key, []).append(x)
    return sig

langs = {
    "ends in ab":               lambda w: w.endswith("ab"),
    "even number of a's":       lambda w: w.count("a") % 2 == 0,
    "contains aba":             lambda w: "aba" in w,
    "a^n b^n":                  lambda w: w == "a" * (len(w) // 2) + "b" * (len(w) // 2),
}
for name, f in langs.items():
    c = classes(f)
    reps = sorted((min(v, key=lambda s: (len(s), s)) for v in c.values()), key=lambda s: (len(s), s))
    shown = ", ".join(r or "eps" for r in reps[:8]) + (" ..." if len(reps) > 8 else "")
    print(f"{name:22s} {len(c):3d} classes   representatives: {shown}")
print("For a^n b^n the count keeps growing with the prefix length:")
for k in range(2, 9, 2):
    print(f"  prefixes up to length {k}: {len(classes(langs['a^n b^n'], k, k + 2))} classes")

ends in ab               3 classes   representatives: eps, a, ab
even number of a's       2 classes   representatives: eps, a
contains aba             4 classes   representatives: eps, a, ab, aba
a^n b^n                 11 classes   representatives: eps, a, b, aa, ab, aaa, aab, aaaa ...
For a^n b^n the count keeps growing with the prefix length:
  prefixes up to length 2: 5 classes
  prefixes up to length 4: 9 classes
  prefixes up to length 6: 13 classes
  prefixes up to length 8: 17 classes

Minimization

The theorem also says how to minimize a DFA. Two states p and q are equivalent if every string leads both to acceptance or both to rejection. The table-filling algorithm marks pairs that are distinguishable: first every pair with one accepting and one non-accepting state, then, repeatedly, any pair that moves on some symbol to an already marked pair. When nothing new is marked, unmarked pairs are equivalent and can be merged, after removing unreachable states. Hopcroft's partition-refinement algorithm, met in CMPUT-415, computes the same result in \(O(n \log n)\) time. The uniqueness half of Myhill–Nerode means that whichever algorithm is used, the result is the same machine up to renaming, which gives a canonical form for regular languages and a simple equivalence test: minimize both DFAs and compare.

# Table-filling minimization: mark pairs of DFA states that some string distinguishes,
# then merge unmarked pairs. The 6-state DFA tracks value mod 6 and accepts remainders 0 and 3.
from itertools import combinations
Q = list(range(6))
d = {(r, b): (2 * r + int(b)) % 6 for r in Q for b in "01"}
F = {0, 3}
marked = {frozenset(p) for p in combinations(Q, 2) if (p[0] in F) != (p[1] in F)}
rounds = 0
while True:
    rounds += 1
    new = {frozenset((p, q)) for p, q in combinations(Q, 2)
           if frozenset((p, q)) not in marked
           and any(frozenset((d[(p, c)], d[(q, c)])) in marked for c in "01")}
    if not new: break
    marked |= new
print("rounds of marking:", rounds)
unmarked = [tuple(sorted(p)) for p in combinations(Q, 2) if frozenset(p) not in marked]
print("equivalent pairs:", unmarked)
blocks, seen = [], set()
for q in Q:
    if q in seen: continue
    block = {q} | {r for r in Q if frozenset((q, r)) not in marked and r != q}
    seen |= block; blocks.append(sorted(block))
print("merged states:", blocks)
print("minimal DFA size:", len(blocks), "(the divisible-by-3 DFA of lesson 2)")

rounds of marking: 2
equivalent pairs: [(0, 3), (1, 4), (2, 5)]
merged states: [[0, 3], [1, 4], [2, 5]]
minimal DFA size: 3 (the divisible-by-3 DFA of lesson 2)

Worked examples