Subset construction in Python
Builds a DFA whose states are sets of NFA states, yielding an equivalent deterministic automaton.
- File
subset_construction.py, 67 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/subset-construction/. The authors are listed in prov/19CF15.jsonl.
from collections import deque
from collections.abc import Iterable, Mapping
EPS = "" # the label of an epsilon-move
State = int
Delta = Mapping[tuple[State, str], Iterable[State]]
def close(states: Iterable[State], delta: Delta) -> frozenset[State]:
"""Return the epsilon-closure of a set of states.
The closure holds each state that a path of epsilon-moves reaches from the set.
It uses an explicit stack, so deep chains of epsilon-moves need no recursion.
Cost: O(n + m_eps), with m_eps the number of epsilon-moves.
"""
c = set(states) # @line L11
k = list(c)
while k: # @line L12
q = k.pop() # @line L13
for r in delta.get((q, EPS), ()): # @line L14
if r not in c:
c.add(r)
k.append(r)
return frozenset(c) # @line L15
def subset_construction(
alphabet: Iterable[str],
delta: Delta,
start: State,
accepting: Iterable[State],
) -> tuple[list[frozenset[State]], list[dict[str, int]], set[int]]:
"""Build a complete DFA with the same language as an NFA.
The NFA has the transitions delta[(q, a)] -> states, where a == "" marks an
epsilon-move, the start state `start` and the accepting states `accepting`.
The DFA states are the reachable sets of NFA states. The result is
(subsets, table, final): DFA state i is the set subsets[i], its move on a is
table[i][a], the start is state 0, and `final` holds the accepting states.
The empty set, when it is reachable, is the dead state, so the DFA is complete.
Cost: O(N * sigma * (n + m)) time for N DFA states, so O(2^n * sigma * (n + m)).
"""
sigma = list(dict.fromkeys(alphabet))
acc = set(accepting)
s0 = close([start], delta) # @line L1
index: dict[frozenset[State], int] = {s0: 0} # @line L2
subsets: list[frozenset[State]] = [s0]
table: list[dict[str, int]] = [{}]
work = deque([s0])
while work: # @line L3
s = work.popleft() # @line L4
i = index[s]
for a in sigma: # @line L5
step = {r for q in s for r in delta.get((q, a), ())}
t = close(step, delta) # @line L6
if t not in index: # @line L7
index[t] = len(subsets)
subsets.append(t)
table.append({})
work.append(t)
table[i][a] = index[t] # @line L8
final = {i for i, s in enumerate(subsets) if s & acc} # @line L9
return subsets, table, final # @line L10
test_subset_construction.py 118 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/subset-construction/. The authors are listed in prov/19CF15.jsonl.
import itertools
import random
from subset_construction import EPS, close, subset_construction
def words(alphabet, max_len):
for k in range(max_len + 1):
for t in itertools.product(alphabet, repeat=k):
yield "".join(t)
def nfa_accepts(delta, start, accepting, w):
"""Oracle: search the configurations (state, position), with epsilon-moves."""
seen = {(start, 0)}
stack = [(start, 0)]
while stack:
q, i = stack.pop()
if i == len(w) and q in accepting:
return True
nxt = [(r, i) for r in delta.get((q, EPS), ())]
if i < len(w):
nxt += [(r, i + 1) for r in delta.get((q, w[i]), ())]
for c in nxt:
if c not in seen:
seen.add(c)
stack.append(c)
return False
def dfa_accepts(table, final, w):
s = 0
for a in w:
s = table[s][a]
return s in final
def check(alphabet, delta, start, accepting, n_states, max_len=6):
subsets, table, final = subset_construction(alphabet, delta, start, accepting)
assert len(subsets) == len(set(subsets)) <= 2**n_states
for i, s in enumerate(subsets):
assert close(s, delta) == s
assert set(table[i]) == set(alphabet)
assert (i in final) == bool(s & set(accepting))
for w in words(alphabet, max_len):
assert dfa_accepts(table, final, w) == nfa_accepts(delta, start, set(accepting), w), w
return subsets, table, final
def test_example():
# a*b* union (ab)*, with epsilon-moves
delta = {(0, EPS): [1, 3], (1, "a"): [1], (1, EPS): [2], (2, "b"): [2], (3, "a"): [4], (4, "b"): [3]}
subsets, table, final = check("ab", delta, 0, {2, 3}, 5, 8)
assert subsets == [
frozenset({0, 1, 2, 3}),
frozenset({1, 2, 4}),
frozenset({2}),
frozenset({1, 2}),
frozenset({2, 3}),
frozenset(),
frozenset({4}),
frozenset({3}),
]
assert final == {0, 1, 2, 3, 4, 7}
assert table[1] == {"a": 3, "b": 4} and table[7] == {"a": 6, "b": 5}
def test_nth_from_end_needs_all_subsets():
for n in range(1, 7):
delta = {(0, "a"): [0, 1], (0, "b"): [0]}
for i in range(1, n):
delta[(i, "a")] = [i + 1]
delta[(i, "b")] = [i + 1]
subsets, _, _ = check("ab", delta, 0, {n}, n + 1, 7)
assert len(subsets) == 2**n
def test_edges():
# empty language: no accepting state
subsets, table, final = check("ab", {(0, "a"): [1], (1, "b"): [0]}, 0, set(), 2)
assert final == set()
# Sigma*: one accepting state with loops
subsets, table, final = check("ab", {(0, "a"): [0], (0, "b"): [0]}, 0, {0}, 1)
assert len(subsets) == 1 and final == {0}
# no transitions at all: the dead state appears
subsets, table, final = check("ab", {}, 0, {0}, 1)
assert subsets == [frozenset({0}), frozenset()]
# unreachable states and a dead state
delta = {(0, "a"): [1], (1, "a"): [1], (2, "b"): [0], (3, "a"): [3], (3, "b"): [3]}
subsets, _, _ = check("ab", delta, 0, {1, 2}, 4)
assert all(2 not in s and 3 not in s for s in subsets)
# a cycle of epsilon-moves
delta = {(0, EPS): [1], (1, EPS): [2], (2, EPS): [0], (2, "a"): [3]}
subsets, _, _ = check("ab", delta, 0, {3}, 4)
assert subsets[0] == frozenset({0, 1, 2})
# a long chain of epsilon-moves (no recursion limit)
k = 5000
delta = {(i, EPS): [i + 1] for i in range(k)}
assert close([0], delta) == frozenset(range(k + 1))
def test_random_against_brute_force():
rng = random.Random(1959)
for trial in range(600):
n = rng.randint(1, 5)
alphabet = "ab" if trial % 3 else "abc"
delta = {}
for q in range(n):
for a in list(alphabet) + [EPS]:
p = 0.15 if a == EPS else 0.35
targets = [r for r in range(n) if rng.random() < p]
if targets:
delta[(q, a)] = targets
accepting = {q for q in range(n) if rng.random() < 0.35}
check(alphabet, delta, rng.randrange(n), accepting, n, 5)
What the next level needs
- the tests did not run in this build