Požadavek do praxe: Deterministický KA (DKA): KA, který z každé konfigurace může přejít maximálně do jedné
další.
Definice: Nechť M = (Q, S, R, s, F) je KA. M je KA
bez e-přechodů, pokud pro každé pravidlo pa ® q Î R, kde p, q Î Q, platí:
a Î S (a ¹ e )
Převod
KA na DKA: Myšlenka 1/2
s
p
q
f
a
a
1) Myšlenka: Odstranění e-přechodů
e
e
4/44
a