Add ε-moves to your NFA simulator.
What to build
A program that decides words for an NFA whose moves may be labelled eps.
Requirements
- A move labelled
epschanges state without reading a symbol. - Use the ε-closure at the start and after each symbol, and print
acceptorrejectfor each word.
Input
Line 1: start state. Line 2: accepting states. Line 3: t, then t lines from symbol to (symbol may be eps). 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:
A
B
3
A a A
A eps B
B b B
3
aabb
ba
Output:
accept
accept
reject
Why it works
After each step the machine may silently slide along ε-moves, so the closure gives every state it could really be in.
Examples
Example 1 · Input
A B 3 A a A A eps B B b B 3 aabb ba
Expected output
accept accept reject
Example 2 · Input
S U V 5 S eps U S eps V U a U2 U2 b U V a V 2 abab aba
Expected output
accept reject
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Write closure(states): follow "eps" moves with a stack until no new state appears.
Hint 2
Take the closure of the start set, and again after every symbol.
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)
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 seen
for _ in range(int(input())):
current = closure({start})
for symbol in input():
current = closure(set().union(*(delta.get((q, symbol), set()) for q in current)))
print("accept" if current & accepting else "reject")