•
For every
FA
M
, there is an equivalent DFA
M
d
.
Proof
is based on these
conversions:
Finite Automaton
M
e
-free
Finite Automaton
M
’
DFA
M
d
L
(
M
) =
L
(
M
’
)
L
(
M
’
) =
L
(
M
d
)
Theorem
6
/44