Non-Regular Languages and DFA Minimisation — The Pumping Lemma, Myhill–Nerode and Table Filling

Finite automata have finite memory. So some languages — those that need to count without limit — can't be regular. This lesson shows how to prove that, and the flip side: how to make a DFA as small as possible.

1. The intuition: finite memory must repeat

A DFA with p states reading a string of length ≥ p visits p + 1 states, so some state repeats (pigeonhole!). The part of the input between the two visits forms a loop — and loops can be traversed any number of times without the DFA noticing.

2. The pumping lemma for regular languages

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

1. |y| ≥ 1 (the loop is not empty)
2. |xy| ≤ p (the loop happens within the first p symbols)
3. xyⁱz ∈ L for every i ≥ 0 (pump it up or down)

To prove L is not regular (by contradiction):

1. Assume L is regular with pumping length p.
2. Choose a string s ∈ L with |s| ≥ p (cleverly — this is your move).
3. Show that for every split xyz obeying rules 1–2, some i makes xyⁱz ∉ L.
4. Contradiction ⇒ L is not regular.

3. Example: L = {aⁿbⁿ | n ≥ 0}

Choose s = aᵖbᵖ. Since |xy| ≤ p, both x and y lie in the a's: y = aᵏ with k ≥ 1. Pump i = 2: xy²z = aᵖ⁺ᵏbᵖ — more a's than b's, not in L. Contradiction. aⁿbⁿ is not regular.

We can't run "for every p" on a computer, but we can check the key step — that every legal split fails — for a specific p:

def in_L(s):                        # a^n b^n
    n = len(s) // 2
    return s == "a" * n + "b" * n

def every_split_breaks(s, p, in_lang):
    for xy_len in range(1, p + 1):              # |xy| <= p
        for y_len in range(1, xy_len + 1):      # |y| >= 1
            x, y, z = s[:xy_len - y_len], s[xy_len - y_len:xy_len], s[xy_len:]
            if all(in_lang(x + y * i + z) for i in range(0, 4)):
                return False, (x, y, z)         # this split survives pumping
    return True, None

for p in [3, 5, 8]:
    s = "a" * p + "b" * p
    print(f"p={p}: s=a^{p}b^{p}, every split breaks:", every_split_breaks(s, p, in_L)[0])

p=3: s=a^3b^3, every split breaks: True
p=5: s=a^5b^5, every split breaks: True
p=8: s=a^8b^8, every split breaks: True

4. More classic non-regular languages

Checking two of them the same way (each code block here is a complete program):

def every_split_breaks(s, p, in_lang):
    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:]
            if all(in_lang(x + y * i + z) for i in range(0, 4)):
                return False
    return True

is_pal = lambda s: s == s[::-1]
ab_regular = lambda s: s.count("a") % 2 == 0          # a REGULAR language: even number of a's

print("palindromes, s = a^4 b a^4:", every_split_breaks("aaaabaaaa", 4, is_pal))
print("even #a's, s = aaaa (p=4):", every_split_breaks("aaaa", 4, ab_regular), "<- some split survives (y = aa), as expected for a regular language")

palindromes, s = a^4 b a^4: True
even #a's, s = aaaa (p=4): False <- some split survives (y = aa), as expected for a regular language

Important: the pumping lemma can only prove a language is not regular. A language passing the pumping conditions might still be non-regular.

5. Myhill–Nerode: the "how many states?" theorem

Two strings x and y are distinguishable for L if some suffix z puts exactly one of xz, yz in L. Myhill–Nerode: L is regular iff it has finitely many pairwise-distinguishable classes — and the number of classes is exactly the minimum number of DFA states.

For aⁿbⁿ, the strings a, aa, aaa, … are all distinguishable (suffix bⁱ accepts only aⁱ) → infinitely many classes → not regular.

6. Minimising a DFA

Two states are equivalent if no string leads one to accept and the other to reject. Merge equivalent states:

1. Remove unreachable states.
2. Split states into accepting and non-accepting groups.
3. Repeatedly split any group whose states go to different groups on some symbol.
4. When nothing changes, each group is one state of the minimal DFA.

def minimise(states, alphabet, delta, start, accepting):
    # 1. reachable states only
    reach, todo = {start}, [start]
    while todo:
        q = todo.pop()
        for c in alphabet:
            if delta[(q, c)] not in reach:
                reach.add(delta[(q, c)]); todo.append(delta[(q, c)])
    # 2-3. partition refinement
    groups = [g for g in (reach & accepting, reach - accepting) if g]
    while True:
        index = {q: i for i, g in enumerate(groups) for q in g}
        new = []
        for g in groups:
            buckets = {}
            for q in g:
                key = tuple(index[delta[(q, c)]] for c in alphabet)
                buckets.setdefault(key, set()).add(q)
            new.extend(buckets.values())
        if len(new) == len(groups):
            return sorted(sorted(g) for g in new), sorted(set(states) - reach)
        groups = new

# a 6-state DFA for "ends in 01" with redundant states (E duplicates A, F is unreachable)
delta = {("A", "0"): "B", ("A", "1"): "E", ("B", "0"): "B", ("B", "1"): "C",
         ("C", "0"): "D", ("C", "1"): "E", ("D", "0"): "D", ("D", "1"): "C",
         ("E", "0"): "B", ("E", "1"): "A", ("F", "0"): "A", ("F", "1"): "F"}
groups, unreachable = minimise("ABCDEF", "01", delta, "A", {"C"})
print("unreachable:", unreachable)
print("equivalent groups:", groups, "->", len(groups), "states")

unreachable: ['F']
equivalent groups: [['A', 'E'], ['B', 'D'], ['C']] -> 3 states

The 6-state machine collapses to 3 states — the same minimal DFA we designed by hand in lesson 2 ({A, E} = q0, {B, D} = q1, {C} = q2). The minimal DFA is unique (up to renaming states), which also gives a way to test whether two DFAs/regexes describe the same language: minimise both and compare.

Common mistakes

• Choosing a split xyz yourself in a pumping proof — you must handle every legal split; you only choose s (and i).
• Choosing a string shorter than p, or one not in L.
• Using the pumping lemma to "prove" a language is regular.
• Forgetting to remove unreachable states before minimising.

Quick recap

• Finite memory ⇒ long strings revisit a state ⇒ a pumpable loop.
• Pumping lemma: s = xyz, |y| ≥ 1, |xy| ≤ p, xyⁱz ∈ L for all i ≥ 0 — use it (by contradiction) to show non-regularity: aⁿbⁿ, palindromes, prime lengths, ww.
• Myhill–Nerode: regular ⇔ finitely many distinguishable classes = minimal number of states.
• Minimise: drop unreachable, split accepting/non-accepting, refine until stable, merge groups.