Skills101

AdvancedTheory of Computation (TOC) · Lesson 9 of 14 · Updated ·

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

The pumping lemma and 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.

Stateon 0on 1
→ ABF
BGC
* CAC
DCG
EHF
FCG
GGE
HGC

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

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

New stateon 0on 1
→ {A, E}{B, H}F
{B, H}G* C
* C{A, E}C
FCG
GG{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

4. The same algorithm in 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)
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.

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)}")
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.

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"}))
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

FactDetail
The minimal DFA is uniqueup to renaming states (Myhill–Nerode theorem)
Number of states of the minimal DFA= number of Myhill–Nerode classes of the language
Table filling costO(n²) pairs; a simple version takes O(n²·k·n) time for k symbols
Faster methodHopcroft's algorithm, O(k·n log n)
Remove unreachable states firstotherwise they may be wrongly merged or counted
Dead (trap) statesequivalent 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 what you learned

📝 Quiz: DFA Minimisation (Table Filling)5 questions · instant answers & explanations · +10 XP · counts towards your free certificateTake the quiz →