# DFA and NFA Equivalence Proof

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?

• 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.
– user46107
Oct 17, 2022 at 16:21

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.