# DFA Minimisation by Table Filling — Step-by-Step Marking, Distinguishing Strings and Checking Two DFAs Are Equal

Source: https://skills101.in/learn/theory-of-computation/toc-dfa-minimisation-table-filling — Skills101 free tutorial (Theory of Computation (TOC)). Updated 2026-11-21.

The [pumping lemma and minimisation](https://skills101.in/learn/theory-of-computation/pumping-lemma-dfa-minimisation) lesson minimised a DFA by **splitting groups** (partition refinement). Most university exams and GATE answer keys use a different presentation of the same idea: the **table-filling method**, where you mark pairs of states in a triangular table. This lesson works through a full 8-state example the way you would on paper, then runs the same algorithm in Python so you can check your own answers.

## 1. The idea: which pairs can be told apart?

Two states p and q are **distinguishable** if some input string w takes one of them to an accepting state and the other to a non-accepting state. If no such string exists, p and q are **equivalent** and can be merged into one state without changing the language.

Table filling finds all distinguishable pairs by working **backwards from the accepting states**:

1. **Remove unreachable states** (states no input can reach from the start).
2. Draw a triangular table with one cell for every **pair** of states.
3. **Round 0:** mark every pair where one state is accepting and the other is not. The empty string ε tells them apart.
4. **Round k:** for each unmarked pair (p, q) and each symbol a, look at the pair (δ(p, a), δ(q, a)). If **that** pair is already marked, mark (p, q). (Reading a takes p and q to states that can be told apart, so p and q can be told apart too — by one more symbol.)
5. Repeat until a round marks nothing new.
6. Every **unmarked** pair is equivalent. Merge them.

A pair marked in round k has a distinguishing string of length exactly k. That is why the marks spread outwards from the accepting states, one symbol at a time.

## 2. The example machine

This 8-state DFA over {0, 1} is a classic textbook exercise. Start state A, accepting state C.

| State | on 0 | on 1 |
|---|---|---|
| → A | B | F |
| B | G | C |
| * C | A | C |
| D | C | G |
| E | H | F |
| F | C | G |
| G | G | E |
| H | G | C |

**Step 1 — reachability.** From A we reach B and F; from those G, C, E; from E we reach H. **Nothing goes to D**, so D is unreachable and is deleted. Seven states remain: A, B, C, E, F, G, H, giving 7·6/2 = **21 pairs**.

## 3. Filling the table round by round

**Round 0.** C is the only accepting state, so every pair containing C is marked: (A,C), (B,C), (C,E), (C,F), (C,G), (C,H) — 6 pairs.

**Round 1.** Check each of the other 15 pairs. For example:

- (A, B): on 1, A → F and B → C. The pair (C, F) is marked, so **mark (A, B)**.
- (A, E): on 0, A → B and E → H, giving (B, H), not marked yet. On 1, both go to F. **Leave it.**
- (B, H): on 0 both go to G; on 1 both go to C. **Leave it** — these two will never be separated.

Round 1 marks 11 pairs in total.

**Round 2.** (A, G): on 1, A → F and G → E, and (E, F) was marked in round 1, so **mark (A, G)**. In the same way (E, G) is marked.

**Round 3.** Nothing new is marked, so we stop.

![Triangular table-filling chart for the 7 reachable states A, B, C, E, F, G, H: cells marked 0 contain the accepting state C, most other cells are marked in round 1, the pairs A-G and E-G are marked in round 2, and only A-E and B-H stay unmarked, so they are equivalent](https://skills101.in/learn-img/theory-of-computation/table-filling.svg)

Only **(A, E)** and **(B, H)** are unmarked. Merging them gives five states:

| New state | on 0 | on 1 |
|---|---|---|
| → {A, E} | {B, H} | F |
| {B, H} | G | * C |
| * C | {A, E} | C |
| F | C | G |
| G | G | {A, E} |

![The minimal DFA with five states: AE is the start, C is the only accepting state; AE goes to BH on 0 and F on 1; BH goes to G on 0 and C on 1; C goes to AE on 0 and loops on 1; F goes to C on 0 and G on 1; G loops on 0 and goes to AE on 1](https://skills101.in/learn-img/theory-of-computation/min-dfa-five.svg)

## 4. The same algorithm in Python

```python
from itertools import combinations
from collections import deque

delta = {"A": {"0": "B", "1": "F"}, "B": {"0": "G", "1": "C"}, "C": {"0": "A", "1": "C"},
         "D": {"0": "C", "1": "G"}, "E": {"0": "H", "1": "F"}, "F": {"0": "C", "1": "G"},
         "G": {"0": "G", "1": "E"}, "H": {"0": "G", "1": "C"}}
start, accepting = "A", {"C"}

reach, queue = {start}, deque([start])          # step 1: reachable states
while queue:
    s = queue.popleft()
    for t in delta[s].values():
        if t not in reach:
            reach.add(t)
            queue.append(t)
states = sorted(reach)
print("unreachable:", sorted(set(delta) - reach))

marked = {pair: 0 for pair in combinations(states, 2) if (pair[0] in accepting) != (pair[1] in accepting)}
print("round 0 marks:", len(marked), "pairs")
rnd = 0
while True:
    rnd += 1
    new = {}
    for p, q in combinations(states, 2):
        if (p, q) in marked:
            continue
        for c in "01":
            pair = tuple(sorted((delta[p][c], delta[q][c])))
            if pair[0] != pair[1] and pair in marked:
                new[(p, q)] = rnd
                break
    if not new:
        break
    print(f"round {rnd} marks: {len(new)} pairs", *([sorted(new)] if len(new) < 5 else []))
    marked.update(new)

equivalent = [pair for pair in combinations(states, 2) if pair not in marked]
print("equivalent pairs:", equivalent)
```

```text
unreachable: ['D']
round 0 marks: 6 pairs
round 1 marks: 11 pairs
round 2 marks: 2 pairs [('A', 'G'), ('E', 'G')]
equivalent pairs: [('A', 'E'), ('B', 'H')]
```

Notice that a new round only uses marks from **earlier** rounds. That keeps the round number equal to the length of the shortest distinguishing string, which the next section uses.

## 5. Finding the string that tells two states apart

A mark in the table is a promise: "some string distinguishes these two states". A **breadth-first search** over pairs of states finds the **shortest** such string. Start from the pair, try each symbol, and stop at the first pair where exactly one state accepts.

```python
from collections import deque

delta = {"A": {"0": "B", "1": "F"}, "B": {"0": "G", "1": "C"}, "C": {"0": "A", "1": "C"},
         "E": {"0": "H", "1": "F"}, "F": {"0": "C", "1": "G"},
         "G": {"0": "G", "1": "E"}, "H": {"0": "G", "1": "C"}}
accepting = {"C"}

def distinguish(p, q):
    seen, queue = {(p, q)}, deque([(p, q, "")])
    while queue:
        x, y, w = queue.popleft()
        if (x in accepting) != (y in accepting):
            return w or "ε"
        for c in "01":
            nxt = (delta[x][c], delta[y][c])
            if nxt not in seen:
                seen.add(nxt)
                queue.append((*nxt, w + c))
    return None                                   # equivalent: no string works

for p, q in [("A", "C"), ("A", "B"), ("A", "G"), ("E", "G"), ("A", "E"), ("B", "H")]:
    print(f"{p},{q}: {distinguish(p, q)}")
```

```text
A,C: ε
A,B: 1
A,G: 01
E,G: 01
A,E: None
B,H: None
```

- (A, B) is told apart by `1`: from A, reading 1 reaches F (reject); from B it reaches C (accept). Length 1 = round 1.
- (A, G) needs `01`: from A, 0 then 1 reaches C (accept); from G it reaches E (reject). Length 2 = round 2.
- (A, E) and (B, H) return `None`: no string separates them, which confirms the merge.

Writing the distinguishing string next to each mark is a good way to show your working in an exam answer.

## 6. Are two DFAs equal?

The same pair search answers a bigger question: **do two DFAs accept exactly the same language?** Run both machines together from their start states (the product construction). If you ever reach a pair where one accepts and the other rejects, the path to it is a **counterexample**. If no such pair is reachable, the DFAs are equivalent.

```python
from collections import deque

def equivalent(d1, s1, f1, d2, s2, f2, alphabet="01"):
    seen, queue = {(s1, s2)}, deque([(s1, s2, "")])
    while queue:
        x, y, w = queue.popleft()
        if (x in f1) != (y in f2):
            return False, w or "ε"
        for c in alphabet:
            nxt = (d1[x][c], d2[y][c])
            if nxt not in seen:
                seen.add(nxt)
                queue.append((*nxt, w + c))
    return True, None

original = {"A": {"0": "B", "1": "F"}, "B": {"0": "G", "1": "C"}, "C": {"0": "A", "1": "C"},
            "D": {"0": "C", "1": "G"}, "E": {"0": "H", "1": "F"}, "F": {"0": "C", "1": "G"},
            "G": {"0": "G", "1": "E"}, "H": {"0": "G", "1": "C"}}
minimal = {"AE": {"0": "BH", "1": "F"}, "BH": {"0": "G", "1": "C"}, "C": {"0": "AE", "1": "C"},
           "F": {"0": "C", "1": "G"}, "G": {"0": "G", "1": "AE"}}
print("original vs minimal:", equivalent(original, "A", {"C"}, minimal, "AE", {"C"}))

wrong = {k: dict(v) for k, v in minimal.items()}
wrong["G"]["1"] = "G"                             # a copying mistake in one cell
print("original vs wrong:  ", equivalent(original, "A", {"C"}, wrong, "AE", {"C"}))
```

```text
original vs minimal: (True, None)
original vs wrong:   (False, '00101')
```

The second check catches a one-cell mistake and even gives the input to try by hand. Use this to test your answers when you practise: if your minimal DFA is not equivalent to the original, the counterexample shows where you went wrong.

## 7. Facts to remember

| Fact | Detail |
|---|---|
| The minimal DFA is unique | up to renaming states (Myhill–Nerode theorem) |
| Number of states of the minimal DFA | = number of Myhill–Nerode classes of the language |
| Table filling cost | O(n²) pairs; a simple version takes O(n²·k·n) time for k symbols |
| Faster method | Hopcroft's algorithm, O(k·n log n) |
| Remove unreachable states first | otherwise they may be wrongly merged or counted |
| Dead (trap) states | equivalent dead states merge into one |

## Common mistakes

- Skipping the reachability step. An unreachable state can look equivalent to a real one and give the wrong number of states.
- In round 0, marking pairs of two accepting states. Round 0 marks only accepting/non-accepting pairs.
- Marking (p, q) because δ(p, a) and δ(q, a) are **different** states. They must form a pair that is already **marked**.
- Stopping after one pass. Keep going until a full round marks nothing.
- Forgetting to redirect transitions after merging: every arrow into A or E must now go to {A, E}.

## Quick recap

- Remove unreachable states; list all pairs in a triangular table.
- Round 0: mark accepting/non-accepting pairs. Round k: mark (p, q) if some symbol leads to an already-marked pair.
- Stop when a round adds nothing; unmarked pairs are equivalent and are merged.
- A pair marked in round k has a shortest distinguishing string of length k; BFS over pairs finds it.
- The same BFS on two machines tests DFA equivalence and returns a counterexample if they differ.


Practice quiz and free certificate: https://skills101.in/learn/theory-of-computation/toc-dfa-minimisation-table-filling