Definice: Nechť M = (Q, S, R, s, F) je KA bez e-přechodů. M je deterministický konečný automat (DKA), pokud pro každé pa ® q Î R platí, že množina R – {pa ® q} neobsahuje žádné pravidlo s levou stranou pa.
Převod KA na DKA: Myšlenka 2/2
 2) Myšlenka: Odstranění nedeterminismu
a
...
...
...
p
q1
q2
a
p
a
{q1, q2}
...
...
Nový stav
5/44