import collections as c

# --- INPUT ---
n = int(input("Enter number of states: "))
S = set(input("Enter state names (space separated): ").split())
m = int(input("Enter number of input symbols: "))
A = input("Enter symbols (space separated): ").split()
print("\nEnter transition table:")
T = {s: {a: input(f"δ({s}, {a}) = ") for a in A} for s in S}
s0 = input("\nEnter start state: ")
F = set(input("Enter final states (space separated): ").split())

# --- MINIMIZATION ---
P = {s: s in F for s in S}
while 1:
    N = {s: (P[s], tuple(P[T[s][a]] for a in A)) for s in S}
    u = sorted(set(N.values()))
    P2 = {s: u.index(N[s]) for s in S}
    if P2 == P: break
    P = P2

blocks = c.defaultdict(set)
for s, i in P.items(): blocks[i].add(s)
ms = [frozenset(b) for b in blocks.values()]
m_s0 = next(p for p in ms if s0 in p)
m_F = [p for p in ms if p & F]
m_T = {p: {a: next(q for q in ms if T[next(iter(p))][a] in q) for a in A} for p in ms}

# --- OUTPUT ---
print("\n--- Minimized DFA ---\nStates:")
for s in ms: print(s)
print(f"\nStart State: {m_s0}\nFinal States: {m_F}\n\nTransition Table:")
for p in m_T:
    for a in A: print(f"{p} --{a}--> {m_T[p][a]}")