Find out how many states a language really needs.
What to build
A program that prints the number of states of the minimal DFA equivalent to the given complete DFA.
Requirements
- Ignore unreachable states.
- Print one number.
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 number.
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:
2
Why it works
Each group left by partition refinement is one state of the minimal DFA, so counting groups gives its size.
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
2
Example 2 · Input
0 1 r0 r0 6 r0 0 r0 r0 1 r1 r1 0 r2 r1 1 r0 r2 0 r1 r2 1 r2
Expected output
3
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Remove unreachable states first, then split the groups [accepting, non-accepting] by signature until they stop changing.
Hint 2
A state's signature is the tuple of group numbers its moves lead to, in alphabet order.
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
print(len(groups))