Run the subset construction and count the DFA states it really needs.
What to build
A program that counts the reachable states of the DFA built from an NFA.
Requirements
- Count only the sets reachable from the start set, including ∅ if it is reached.
- Print
dfa states K.
Input
Line 1: the alphabet, separated by spaces. Line 2: start state. Line 3: accepting states. Line 4: t, then t lines from symbol to.
Output
One line: dfa states K.
Constraints
At most 10 NFA states and 40 transitions; no ε-moves.
Example
Input:
a b
0
3
7
0 a 0
0 b 0
0 a 1
1 a 2
1 b 2
2 a 3
2 b 3
Output:
dfa states 8
Why it works
Each reachable set of NFA states is one DFA state, so counting the sets the search finds counts the DFA's states.
Examples
Example 1 · Input
a b 0 3 7 0 a 0 0 b 0 0 a 1 1 a 2 1 b 2 2 a 3 2 b 3
Expected output
dfa states 8
Example 2 · Input
a b s y 4 s a s s b s s a x x b y
Expected output
dfa states 3
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Start from frozenset({start}) and explore with a queue, computing the move on every symbol.
Hint 2
The empty set counts as a state when it is reached.
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.setdefault((a, symbol), set()).add(b)
first = frozenset({start})
seen = {first}
queue = [first]
while queue:
S = queue.pop(0)
for c in alphabet:
T = frozenset(set().union(*(delta.get((q, c), set()) for q in S)))
if T not in seen:
seen.add(T)
queue.append(T)
print("dfa states", len(seen))