Let's say we have a NFA such as follows:
We know it's equivalent DFA is follows, after minimization:
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?
