Odstranění nedeterminismu
Myšlenka: Vytvořit stavy ze všech podmnožin množiny stavů KA bez e-přechodů a přidat přechody mezi nimi tak, aby simulovaly přechody původního automatu.
q1
s
b
f
b
c
c
a
q2
a
b
b
c
c
Ilustrace:
QDKA = {{s}, {q1}, {q2}, { f}, {s,q1}, {s,q2}, {s, f}, {q1,q2}, {q1, f}, {q2, f}, {s,q1,q2}, {s,q1, f}, {s,q2, f}, {q1,q2, f}, {s,q1,q2, f}}
a
c
{q2, f }
...
{q1, f }
b
...
Pro stav {s, f}:
{s, f}
Pro stav {s}: …
...
...
Pro stav {s,q1,q2, f}: …
14/44