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