Theory: Show a DFA's run

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-> state for every move, then accept or reject.
  • If a move is missing, print -symbol-> dead reject and 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))

Lesson: Deterministic finite automata (DFA) →