AlgoVerse

DFA minimization

Merge the equivalent states of a deterministic machine: start from accepting versus non-accepting and split the blocks until no more splits happen.

Two states are equivalent if for every input string either both reach acceptance or neither does. Equivalent states can be merged; the result is the minimal machine, which is unique for each regular language (up to naming the states).

Read the full explanation ↓
Input:
delta 5×3PDF export

A 5-state machine for “ends with ab”; state 3 is equivalent to 0 and state 4 to 1, so the minimal DFA has 3 states. Each row: [after a, after b, accepting].

  1. def minimize(delta):
  2. # delta: one row per state: [state after a, state after b, accepting (1) or not (0)].
  3. n = len(delta)
  4. if any(t >= n for row in delta for t in row[:2]):
  5. return None
  6. block = [1 if row[2] else 0 for row in delta]
  7. table = [[q, delta[q][0], delta[q][1], block[q]] for q in range(n)]
  8. while True:
  9. # Two states stay together only if their blocks agree and so do the blocks they go to.
  10. signature = [(block[q], block[delta[q][0]], block[delta[q][1]]) for q in range(n)]
  11. kinds = sorted(set(signature))
  12. new = [kinds.index(sig) for sig in signature]
  13. for q in range(n):
  14. table[q][3] = new[q]
  15. if len(kinds) == len(set(block)):
  16. break
  17. block = new
  18. return len(set(block))

Invariant: Two states in different blocks are never equivalent: some string leads one of them to acceptance and the other not.

Start

block—

The table is still empty.

Local variables

Orange = changed in this step

delta list

[1, 3, 0][1, 2, 0][1, 3, 1][4, 3, 0][4, 2, 0]

Call stack

  1. minimize()line 1
Step 1 of 40
Black = refined, stable · Orange = key stepsplit_accepting: 0/1 · refined: 0/1 · stable: 0/1
    Explanation

    The idea

    Two states are equivalent if for every input string either both reach acceptance or neither does. Equivalent states can be merged; the result is the minimal machine, which is unique for each regular language (up to naming the states).

    Partition refinement (Moore's method)

    1. Split the states into two blocks: accepting and non-accepting (the empty string tells them apart).
    2. Split each block: two states stay together only if on a they go to the same block, and on b too.
    3. Repeat while some block splits. When none does, each block is one state of the minimal machine.

    Cost

    At most n rounds of O(n) each: O(n²). Hopcroft's method picks the blocks cleverly and reaches O(n log n).

    The input

    Each row is a state: [after a, after b, accepting (1) or not (0)]; the start state is 0.