I'm taking a Theory of Computation class and we went over the proof to show that for any NFA there is an equivalent DFA, which I understand the proof fully in this case. But if it were in reverse, for example, "For any DFA, there is an equivalent NFA," how different would the NFA -> DFA proof be to the DFA -> NFA proof? Or is it basically the same thing?
1
-
$\begingroup$ A state in a DFA has exactly one transition (outgoing edge) for each input symbol (when no transition for a symbol is given explicitly, it typically indicates the state does not change, a "null transition" that is drawn as a little circular arrow in a diagram; formally, the "transition" exists). An NFA is defined almost identically, but allows multiple transitions out of a state for a given symbol, with the non-deterministic interpretation being simultaneously in a set of states. A DFA is an NFA with exactly one transition out of each state, which naturally has no non-deterministic behavior. $\endgroup$– user46107Commented Oct 17, 2022 at 16:21
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
The proof would be trivial: all DFAs are also NFAs.
If you somehow insist in proving that for every DFA there exists an equivalent NFA that is not also a DFA, then it suffices to add a new initial state $q$ along with an $\varepsilon$-transition from $q$ to the old initial state.
$\begingroup$
$\endgroup$
Every DFA is an NFA by definition, so you only need to prove that for every NFA there exists an equivalent DFA.
