Moore's DFA minimization algorithm in Python
Minimizes a DFA by repeatedly splitting state classes by successor class until stable, in O(n^2) time for a fixed alphabet.
- File
moore_minimization.py, 56 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/moore-minimization/. The authors are listed in prov/7CHN37.jsonl.
from collections.abc import Sequence
from typing import NamedTuple
class DFA(NamedTuple):
"""A complete DFA: states 0..n-1, symbols 0..sigma-1, delta[q][a] is the next state."""
delta: list[list[int]]
start: int
finals: frozenset[int]
def reachable(delta: Sequence[Sequence[int]], start: int) -> list[int]:
"""The states reachable from start, by an iterative depth-first search; O(n sigma) time."""
seen = {start}
stack = [start]
order = [start]
while stack:
q = stack.pop()
for r in delta[q]:
if r not in seen:
seen.add(r)
stack.append(r)
order.append(r)
return sorted(order)
def moore_minimize(delta: Sequence[Sequence[int]], start: int, finals: set[int] | frozenset[int]) -> tuple[DFA, dict[int, int]]:
"""Minimize a complete DFA by Moore's partition refinement.
Returns the minimal complete DFA and the map from each reachable state of the
input to its state in the output. Each round costs O(n sigma) expected time with
hashing, and there are at most n - 1 rounds, so the time is O(sigma n^2).
"""
sigma = len(delta[0]) if delta else 0
states = reachable(delta, start) # @line L1
cls = {q: (1 if q in finals else 0) for q in states} # @line L2
k = len(set(cls.values())) # @line L3
while True: # @line L4
sig = {q: (cls[q],) + tuple(cls[delta[q][a]] for a in range(sigma)) for q in states} # @line L5
number: dict[tuple[int, ...], int] = {}
new = {q: number.setdefault(sig[q], len(number)) for q in states} # @line L6
k_new = len(number) # @line L7
stable = k_new == k # @line L8
cls, k = new, k_new # @line L9
if stable: # @line L10
break
out = [[0] * sigma for _ in range(k)] # @line L11
for q in states:
for a in range(sigma):
out[cls[q]][a] = cls[delta[q][a]]
out_finals = frozenset(cls[q] for q in states if q in finals)
return DFA(out, cls[start], out_finals), cls
test_moore_minimization.py 85 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/moore-minimization/. The authors are listed in prov/7CHN37.jsonl.
import itertools
import random
from moore_minimization import moore_minimize, reachable
def accepts(delta, start, finals, word) -> bool:
q = start
for a in word:
q = delta[q][a]
return q in finals
def words(sigma: int, max_len: int):
for n in range(max_len + 1):
yield from itertools.product(range(sigma), repeat=n)
def brute_min_size(delta, start, finals) -> int:
"""Count reachable states with distinct acceptance on all words of length <= n."""
n, sigma = len(delta), len(delta[0])
ws = list(words(sigma, n))
return len({tuple(accepts(delta, q, finals, w) for w in ws) for q in reachable(delta, start)})
def check(delta, start, finals) -> None:
m, cls = moore_minimize(delta, start, finals)
n, sigma = len(delta), len(delta[0])
assert len(m.delta) == brute_min_size(delta, start, finals)
# two DFAs with n and k states that differ also differ on a word of length <= n + k - 2
for w in words(sigma, max(0, n + len(m.delta) - 2)):
assert accepts(delta, start, finals, w) == accepts(m.delta, m.start, m.finals, w)
for q, c in cls.items():
for a in range(sigma):
assert m.delta[c][a] == cls[delta[q][a]]
def test_example() -> None:
delta = [[1, 2], [3, 4], [4, 3], [5, 5], [5, 5], [5, 5], [6, 3]]
m, cls = moore_minimize(delta, 0, {3, 4, 6})
assert m.delta == [[1, 1], [2, 2], [3, 3], [3, 3]]
assert m.start == 0 and m.finals == frozenset({2})
assert cls == {0: 0, 1: 1, 2: 1, 3: 2, 4: 2, 5: 3}
check(delta, 0, {3, 4, 6})
def test_edges() -> None:
# empty language, Sigma*, one state, unreachable and dead states
m, _ = moore_minimize([[0, 0]], 0, set())
assert len(m.delta) == 1 and not m.finals
m, _ = moore_minimize([[0, 0]], 0, {0})
assert len(m.delta) == 1 and m.finals == frozenset({0})
m, _ = moore_minimize([[1], [0], [2]], 0, {2})
assert len(m.delta) == 1 and not m.finals
m, _ = moore_minimize([[1, 1], [0, 0]], 0, {0, 1})
assert len(m.delta) == 1 and m.finals == frozenset({0})
for delta, f in (([[1], [2], [2]], {1}), ([[1, 2], [2, 2], [2, 2]], {1}), ([[0]], set())):
check(delta, 0, f)
def test_worst_case_rounds() -> None:
# the chain 0 -> 1 -> ... -> n-1 with F = {n-1} is already minimal
for n in range(1, 9):
delta = [[min(i + 1, n - 1)] for i in range(n)]
m, _ = moore_minimize(delta, 0, {n - 1})
assert len(m.delta) == n
def test_random_against_brute_force() -> None:
rng = random.Random(7377)
for t in range(600):
sigma = rng.randint(1, 3)
n = rng.randint(1, 6 if sigma < 3 else 5)
delta = [[rng.randrange(n) for _ in range(sigma)] for _ in range(n)]
mode = t % 5
if mode == 0:
finals = set()
elif mode == 1:
finals = set(range(n))
else:
finals = {q for q in range(n) if rng.random() < 0.4}
check(delta, rng.randrange(n), finals)
What the next level needs
- the tests did not run in this build