Watch every path of an NFA at once.
What to build
A program that prints the set of possible states after each prefix of one word.
Requirements
- Print the start set, then the set after each symbol, one per line, states sorted alphabetically.
- Print ∅ for an empty set, and finish with
acceptorreject.
Input
Line 1: start state. Line 2: accepting states. Line 3: t, then t lines from symbol to. Line after: one word (may be empty).
Output
One line per prefix, then accept or reject.
Constraints
At most 15 states and 60 transitions; the word has at most 30 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
abb
Output:
0
0 1
0 2
0 3
accept
Why it works
The set after a prefix is exactly the states some path can be in, which is why the final set decides acceptance.
Examples
Example 1 · 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 abb
Expected output
0 0 1 0 2 0 3 accept
Example 2 · Input
s y 4 s a s s b s s a x x b y aba
Expected output
s s x s y s x reject
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Print the sorted states joined by spaces, or ∅ when the set is empty.
Hint 2
Print the starting set before reading any 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 show(states):
return " ".join(sorted(states)) if states else "∅"
current = {start}
print(show(current))
for symbol in input():
current = set().union(*(delta.get((q, symbol), set()) for q in current))
print(show(current))
print("accept" if current & accepting else "reject")