Theory: How many DFA states?

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))

Lesson: From NFA to DFA: the subset construction →