0
$\begingroup$

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?

$\endgroup$
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$
    – user46107
    Oct 17, 2022 at 16:21

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

Every DFA is an NFA by definition, so you only need to prove that for every NFA there exists an equivalent DFA.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.