Write a general DFA simulator that reads the machine from the input.
What to build
A program that reads a DFA and several words and decides each word.
Requirements
- A word whose run needs a transition that is not listed is rejected.
- Print
acceptorrejectfor each word.
Input
Line 1: the start state. Line 2: the accepting states, separated by spaces (possibly none). Line 3: t. Then t lines from symbol to. Then a line with n, then n words (a word may be an empty line).
Output
n lines, each accept or reject.
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
3
110
111
1001
Output:
accept
reject
accept
Why it works
A DFA is fully described by its start state, accepting states and transition table, so one simulator runs them all.
Examples
r0 r0 6 r0 0 r0 r0 1 r1 r1 0 r2 r1 1 r0 r2 0 r1 r2 1 r2 3 110 111 1001
accept reject accept
s f 6 s a A s b s A a A A b f f a f f b f 3 bba abb ba
reject accept reject
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Store δ in a dictionary keyed by (state, symbol); a missing key means the run is stuck.
Hint 2
The accepting line may be empty, meaning no state accepts.
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
for symbol in input():
state = delta.get((state, symbol))
if state is None:
break
print("accept" if state in accepting else "reject")