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