Print the whole run of a DFA, not only the answer.
What to build
A program that prints the path a DFA takes on each word, then whether it accepts.
Requirements
- Print the start state, then
-symbol-> statefor every move, thenacceptorreject. - If a move is missing, print
-symbol-> dead rejectand ignore the rest of the word.
Input
The same format as "Run any DFA": start, accepting states, t transitions, then n words.
Output
One line per word, such as r0 -1-> r1 -1-> r0 accept.
Constraints
At most 20 states, 60 transitions and 20 words of at most 40 symbols.
Example
Input:
r0
r0
6
r0 0 r0
r0 1 r1
r1 0 r2
r1 1 r0
r2 0 r1
r2 1 r2
2
110
111
Output:
r0 -1-> r1 -1-> r0 -0-> r0 accept
r0 -1-> r1 -1-> r0 -1-> r1 reject
Why it works
The run is the sequence of states; printing it shows exactly why a word is accepted or rejected.
Examples
Example 1 · Input
r0 r0 6 r0 0 r0 r0 1 r1 r1 0 r2 r1 1 r0 r2 0 r1 r2 1 r2 2 110 111
Expected output
r0 -1-> r1 -1-> r0 -0-> r0 accept r0 -1-> r1 -1-> r0 -1-> r1 reject
Example 2 · Input
p q 2 p x q q y p 2 xyx xx
Expected output
p -x-> q -y-> p -x-> q accept p -x-> q -x-> dead reject
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Build the output as a list of pieces such as "q0", "-a->", "q1" and join them with spaces.
Hint 2
When a transition is missing, add "-c->" and "dead", then stop reading that word.
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[(a, symbol)] = b
for _ in range(int(input())):
state = start
parts = [state]
for symbol in input():
nxt = delta.get((state, symbol))
parts.append(f"-{symbol}->")
if nxt is None:
state = None
parts.append("dead")
break
parts.append(nxt)
state = nxt
parts.append("accept" if state in accepting else "reject")
print(" ".join(parts))