Theory: Does the NFA accept?

Simulate an NFA without ε-moves by tracking every state it could be in.

What to build

A program that reads an NFA and decides several words.

Requirements

  • Accept when the final set of states contains an accepting state.
  • Print accept or reject for each word.

Input

Line 1: start state. Line 2: accepting states. Line 3: t, then t lines from symbol to (a state and symbol may appear on several lines). Then n and n words (a word may be an empty line).

Output

n lines, each accept or reject.

Constraints

At most 15 states, 60 transitions and 20 words of at most 40 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
3
abb
bab
aaba

Output:

accept
reject
accept

Why it works

A set of states holds every path at once, so no guessing is needed.

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
3
abb
bab
aaba
Expected output
accept
reject
accept
Example 2 · Input
s
y
4
s a s
s b s
s a x
x b y
3
ab
aba
bbab
Expected output
accept
reject
accept

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Keep a set of current states and replace it, after each symbol, by the union of their moves.

Hint 2

A state may be listed with the same symbol on several lines: collect them into a set.

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)
for _ in range(int(input())):
    current = {start}
    for symbol in input():
        current = set().union(*(delta.get((q, symbol), set()) for q in current))
    print("accept" if current & accepting else "reject")

Lesson: Nondeterministic finite automata (NFA) →