Theory: The NFA's set of states

Watch every path of an NFA at once.

What to build

A program that prints the set of possible states after each prefix of one word.

Requirements

  • Print the start set, then the set after each symbol, one per line, states sorted alphabetically.
  • Print ∅ for an empty set, and finish with accept or reject.

Input

Line 1: start state. Line 2: accepting states. Line 3: t, then t lines from symbol to. Line after: one word (may be empty).

Output

One line per prefix, then accept or reject.

Constraints

At most 15 states and 60 transitions; the word has at most 30 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
abb

Output:

0
0 1
0 2
0 3
accept

Why it works

The set after a prefix is exactly the states some path can be in, which is why the final set decides acceptance.

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

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

Hints

Hint 1

Print the sorted states joined by spaces, or ∅ when the set is empty.

Hint 2

Print the starting set before reading any 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 show(states):
    return " ".join(sorted(states)) if states else "∅"


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

Lesson: Nondeterministic finite automata (NFA) →