Simulate an NFA without ε-moves by tracking every state it could be in.
What to build
A program that reads an NFA and decides several words.
Requirements
- Accept when the final set of states contains an accepting state.
- Print
acceptorrejectfor each word.
Input
Line 1: start state. Line 2: accepting states. Line 3: t, then t lines from symbol to (a state and symbol may appear on several lines). Then n and n words (a word may be an empty line).
Output
n lines, each accept or reject.
Constraints
At most 15 states, 60 transitions and 20 words of at most 40 symbols.
Example
Input:
0
3
7
0 a 0
0 b 0
0 a 1
1 a 2
1 b 2
2 a 3
2 b 3
3
abb
bab
aaba
Output:
accept
reject
accept
Why it works
A set of states holds every path at once, so no guessing is needed.
Examples
0 3 7 0 a 0 0 b 0 0 a 1 1 a 2 1 b 2 2 a 3 2 b 3 3 abb bab aaba
accept reject accept
s y 4 s a s s b s s a x x b y 3 ab aba bbab
accept reject accept
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Keep a set of current states and replace it, after each symbol, by the union of their moves.
Hint 2
A state may be listed with the same symbol on several lines: collect them into a set.
Solution
Show one correct solution (try it yourself first)
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)
for _ in range(int(input())):
current = {start}
for symbol in input():
current = set().union(*(delta.get((q, symbol), set()) for q in current))
print("accept" if current & accepting else "reject")