# Is a DFA a subset of NFA? Why?

After reading this previous question Difference between NFA and DFA, it's clearer to me their relationship/differences.

Can one say that a DFA is a subset of a NFA where both recognize a/the same regular language? If so, how can I back my assumption ?

## 2 Answers

Yes every NFA has a corresponding DFA, the process of constructing the DFA from the NFA is called subset construction. In essence each state of the DFA is a set of states of the NFA. The constructed DFA recognizes the same formal languange as the starting NFA.

Yes, that's correct. An NFA is allowed to be in multiple states in once and can have multiple initial/accepting states. It doesn't have to be though; we can construct an NFA to be in only one state at any point in time and have only one initial and one accepting state, so that it is the same as a DFA.

In fact, DFAs and NFAs are actually equivalent. As Brian M. Scott hints at the ends of his post, there is an algorithm that can take any given NFA and construct an equivalent DFA.