• Pro každý KA M, existuje ekvivalentní DKA Md.
Důkaz je založen na následujících převodech:
Konečný automat M
KA bez e-přechodů M’
DKA  Md
L(M) = L(M’)
L(M’) = L(Md)
Tvrzení
6/44