Theory: Minimise a DFA

Produce the minimal DFA itself, not only its size.

What to build

A program that prints the groups of equivalent states that form the minimal DFA.

Requirements

  • Ignore unreachable states; print one group per line, its states sorted and separated by spaces.
  • Add start to the group with the start state and accept to accepting groups.
  • Order the lines by each group's first state.

Input

Line 1: the alphabet. Line 2: start state. Line 3: accepting states. Line 4: t, then t lines from symbol to. The DFA is complete.

Output

One line per state of the minimal DFA.

Constraints

At most 30 states.

Example

Input:

0 1
q0
q2 q3
10
q0 0 q1
q0 1 q2
q1 0 q1
q1 1 q3
q2 0 q1
q2 1 q3
q3 0 q1
q3 1 q2
q4 0 q4
q4 1 q4

Output:

q0 q1 start
q2 q3 accept

Why it works

Equivalent states can be merged because no string tells them apart; the groups are exactly the states of the minimal DFA.

Examples

Example 1 · Input
0 1
q0
q2 q3
10
q0 0 q1
q0 1 q2
q1 0 q1
q1 1 q3
q2 0 q1
q2 1 q3
q3 0 q1
q3 1 q2
q4 0 q4
q4 1 q4
Expected output
q0 q1 start
q2 q3 accept
Example 2 · Input
a b
E
E E2
6
E a O
E b E
O a E2
O b O
E2 a O
E2 b E2
Expected output
E E2 start accept
O

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

After refinement, sort each group, and sort the groups by their first state.

Hint 2

A group is the start group if it contains the start state, and accepting if its states accept.

Solution

Show one correct solution (try it yourself first)
alphabet = input().split()
start = input().strip()
accepting = set(input().split())
delta = {}
for _ in range(int(input())):
    a, symbol, b = input().split()
    delta[(a, symbol)] = b
reach, stack = {start}, [start]
while stack:
    s = stack.pop()
    for c in alphabet:
        t = delta[(s, c)]
        if t not in reach:
            reach.add(t)
            stack.append(t)
groups = [g for g in (sorted(reach & accepting), sorted(reach - accepting)) if g]
while True:
    index = {q: i for i, g in enumerate(groups) for q in g}
    new = []
    for g in groups:
        by_sig = {}
        for q in g:
            by_sig.setdefault(tuple(index[delta[(q, c)]] for c in alphabet), []).append(q)
        new.extend(by_sig.values())
    if len(new) == len(groups):
        break
    groups = new
for g in sorted(sorted(g) for g in groups):
    line = " ".join(g)
    if start in g:
        line += " start"
    if g[0] in accepting:
        line += " accept"
    print(line)

Lesson: Minimising a DFA →