Let's say we have a NFA such as follows: enter image description here

We know it's equivalent DFA is follows, after minimization: enter image description here

We know that when converting from NFA to DFA, the resultant DFA would have around 2^( number of states in NFA ). This is where I get a bit confused: Should we consider the "dead state" of NFA when converting to DFA. Because if we do, we would have 32 states in DFA ( in the above example ) before minimization, and if we don't, then we would have around 16 states in DFA before minimization

According to me, we should not consider the "dead state" of NFA when converting to DFA because, a dead state on a certain branch of computation of NFA just implies that that particular branch has rejected the input so there's no further state on this branch of computation. So, even if we were to consider the "dead state" in NFA, when we would convert the NFA to DFA we would have some states paired up with "dead state" ( in the power set of states )which could imply most of them would end up rejecting input because a dead state will always point back to itself

So when we not consider the "dead state" of NFA during conversion, we still end up with correct DFA because since we have 2^(states of NFA) in DFA, one of them is "phi" which we can use as sink state, because since we aren't considering the "phi" ( dead state ) of NFA, there's no other use of this state in DFA. So, in this case q4 of NFA and epsilon transition of every state of NFA would point to "phi", which, we will change from epsilon to appropriate state in DFA and point q4 to "phi". Also we can minimize this DFA and remove the dead state itself

Am i correct?


1 Answer 1


You can indeed ignore dead states in NFA when doing the conversion. Actually, even without considering the conversion, it is generally common not to draw dead states in NFA (the notion of complete automaton stands for DFA, not for NFA).


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.