Theory: The subset construction table

Print the full transition table of the DFA built from an NFA.

What to build

A program that prints one row per reachable DFA state, in the order a breadth-first search discovers them.

Requirements

  • Each row: the set's name, then symbol=name for each symbol in the given order.
  • End a row with * when the set contains an accepting NFA state.

Input

Line 1: the alphabet, separated by spaces. Line 2: start state. Line 3: accepting states. Line 4: t, then t lines from symbol to.

Output

One row per DFA state, such as {s,x} a={s,x} b={s,y}.

Constraints

At most 8 NFA states and 30 transitions; no ε-moves.

Example

Input:

a b
s
y
4
s a s
s b s
s a x
x b y

Output:

{s} a={s,x} b={s}
{s,x} a={s,x} b={s,y}
{s,y} a={s,x} b={s} *

Why it works

Each row is a DFA state with its moves; together the rows are a complete deterministic machine.

Examples

Example 1 · Input
a b
s
y
4
s a s
s b s
s a x
x b y
Expected output
{s} a={s,x} b={s}
{s,x} a={s,x} b={s,y}
{s,y} a={s,x} b={s} *
Example 2 · Input
x y
p
q
3
p x q
p x p
q y q
Expected output
{p} x={p,q} y=∅
{p,q} x={p,q} y={q} *
∅ x=∅ y=∅
{q} x=∅ y={q} *

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

Hints

Hint 1

Process sets in the order you discover them (a queue), trying the symbols in the order given.

Hint 2

Name a set by its sorted states joined with commas inside braces; the empty set is ∅.

Solution

Show one correct solution (try it yourself first)
alphabet = input().split()
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 name(S):
    return "{" + ",".join(sorted(S)) + "}" if S else "∅"


first = frozenset({start})
seen = {first}
queue = [first]
while queue:
    S = queue.pop(0)
    row = [name(S)]
    for c in alphabet:
        T = frozenset(set().union(*(delta.get((q, c), set()) for q in S)))
        row.append(f"{c}={name(T)}")
        if T not in seen:
            seen.add(T)
            queue.append(T)
    print(" ".join(row) + (" *" if S & accepting else ""))

Lesson: From NFA to DFA: the subset construction →