Theory: An NFA with ε-moves

Add ε-moves to your NFA simulator.

What to build

A program that decides words for an NFA whose moves may be labelled eps.

Requirements

  • A move labelled eps changes state without reading a symbol.
  • Use the ε-closure at the start and after each symbol, and 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 (symbol may be eps). 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:

A
B
3
A a A
A eps B
B b B
3
aabb

ba

Output:

accept
accept
reject

Why it works

After each step the machine may silently slide along ε-moves, so the closure gives every state it could really be in.

Examples

Example 1 · Input
A
B
3
A a A
A eps B
B b B
3
aabb

ba
Expected output
accept
accept
reject
Example 2 · Input
S
U V
5
S eps U
S eps V
U a U2
U2 b U
V a V
2
abab
aba
Expected output
accept
reject

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

Hints

Hint 1

Write closure(states): follow "eps" moves with a stack until no new state appears.

Hint 2

Take the closure of the start set, and again after every symbol.

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)


def closure(states):
    seen = set(states)
    stack = list(states)
    while stack:
        s = stack.pop()
        for t in delta.get((s, "eps"), ()):
            if t not in seen:
                seen.add(t)
                stack.append(t)
    return seen


for _ in range(int(input())):
    current = closure({start})
    for symbol in input():
        current = closure(set().union(*(delta.get((q, symbol), set()) for q in current)))
    print("accept" if current & accepting else "reject")

Lesson: Nondeterministic finite automata (NFA) →