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=namefor 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
a b s y 4 s a s s b s s a x x b y
{s} a={s,x} b={s}
{s,x} a={s,x} b={s,y}
{s,y} a={s,x} b={s} *
x y p q 3 p x q p x p q y q
{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 ""))