6
$\begingroup$

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 ?

$\endgroup$
6
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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