Theory: Run any DFA

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 accept or reject for 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

Example 1 · 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
Expected output
accept
reject
accept
Example 2 · Input
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
Expected output
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")

Lesson: Deterministic finite automata (DFA) →