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

Source: https://skills101.in/learn/theory-of-computation/pumping-lemma-dfa-minimisation — Skills101 free tutorial (Theory of Computation (TOC)). Updated 2026-11-09.

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.

![Pumping lemma intuition: a DFA with p states reading a long string must revisit some state; the substring y read around that loop can be repeated zero or more times and the DFA still ends in the same place](https://skills101.in/learn-img/theory-of-computation/pumping-loop.svg)

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

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

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

| Language | String to choose | Why pumping fails |
|---|---|---|
| balanced parentheses | (ᵖ)ᵖ | same as aⁿbⁿ |
| palindromes over {a, b} | aᵖbaᵖ | pumping the first a's breaks symmetry |
| {aⁿ \| n is prime} | a^q with q prime, q ≥ p + 2 | pumping changes the length to a composite |
| {ww \| w ∈ {a,b}*} | aᵖbaᵖb | halves no longer match |
| equal number of a's and b's | aᵖbᵖ | (or: L ∩ a\*b\* = aⁿbⁿ, closure argument) |

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

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

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

![DFA minimisation by partition refinement: start with two groups, accepting and non-accepting; split a group whenever two of its states move to different groups on the same symbol; repeat until stable, then merge each group into one state](https://skills101.in/learn-img/theory-of-computation/minimisation.svg)

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

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


Practice quiz and free certificate: https://skills101.in/learn/theory-of-computation/pumping-lemma-dfa-minimisation