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:
acceptorreject.
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
a b A B 3 A a A A eps B B b B 2 aabb ba
dfa states 3 accept reject
a b S U V 5 S eps U S eps V U a U2 U2 b U V a V 2 abab aa
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")