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