Theory: Subset construction with ε-moves

Build a DFA from an NFA with ε-moves, then use it.

What to build

A program that builds the DFA for an ε-NFA, reports its size, and runs it on words.

Requirements

  • Print dfa states K, counting reachable sets including ∅ if reached.
  • Then decide each word with the built DFA: accept or reject.

Input

Line 1: the alphabet. Line 2: start state. Line 3: accepting states. Line 4: t, then t lines from symbol to (symbol may be eps). Then n and n words (a word may be an empty line).

Output

dfa states K, then n lines.

Constraints

At most 10 NFA states, 40 transitions and 20 words of at most 40 symbols.

Example

Input:

a b
A
B
3
A a A
A eps B
B b B
2
aabb
ba

Output:

dfa states 3
accept
reject

Why it works

With closures in the right places, each DFA state is exactly the set of NFA states that are live after a prefix.

Examples

Example 1 · Input
a b
A
B
3
A a A
A eps B
B b B
2
aabb
ba
Expected output
dfa states 3
accept
reject
Example 2 · Input
a b
S
U V
5
S eps U
S eps V
U a U2
U2 b U
V a V
2
abab
aa
Expected output
dfa states 6
accept
accept

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

The DFA's start state is the ε-closure of the NFA's start state.

Hint 2

After computing the moves of a set on a symbol, take the ε-closure before using it as a DFA state.

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)


def closure(states):
    seen = set(states)
    stack = list(states)
    while stack:
        s = stack.pop()
        for t in delta.get((s, "eps"), ()):
            if t not in seen:
                seen.add(t)
                stack.append(t)
    return frozenset(seen)


first = closure({start})
seen = {first}
queue = [first]
table = {}
while queue:
    S = queue.pop(0)
    for c in alphabet:
        T = closure(set().union(*(delta.get((q, c), set()) for q in S)))
        table[(S, c)] = T
        if T not in seen:
            seen.add(T)
            queue.append(T)
print("dfa states", len(seen))
for _ in range(int(input())):
    S = first
    for c in input():
        S = table[(S, c)]
    print("accept" if S & accepting else "reject")

Lesson: From NFA to DFA: the subset construction →