# Handling dead state in NFA to DFA conversion

I want to convert below NFA into DFA:

I prepared below tables and finally the NFA:

NFA

However I feel I am wrong here, since original NFA does not have any transitions defined for state C and my final DFA does not have any dead state. However I dont understand where I am going wrong.

## 1 Answer

Your DFA actually looks correct. Why do you need a dead state?

A dead state means the automaton was given a prefix of an input that will never lead to an accepting state. But the language of the NFA has no such prefixes - whatever the prefix is, if you add "10" or "11" you will get to an accepting state.

Anyways, the right thing to do now is to verify that the DFA works fine for several sample inputs. More generally, to prove it actually does decide the language generated by $(0+1)^*1(0+1)$.

• So is my understanding wrong that "if some state in NFA have no transition for any input symbol, then corresponding state in equivalent DFA should have transition to dead state for that particular symbol"? – Maha May 15 '15 at 15:05
• There is no "corresponding state" for $C$ in the DFA, since $C$ always occurs together with other possible NFA states, which provide the possible transitions. If the singleton state $\{C\}$ was reachable in the DFA, it would indeed be a dead state. – Klaus Draeger May 15 '15 at 16:28
• Verify that the DFA works fine for several sample inputs It is not a never-failing way to ensure that your DFA is correct. The best way to be sure is to use an algorithm that has already been proved correctness in transforming a NFA into a DFA like Subset Construction. As long as you execute it well your DFA will be fine. – Renato Sanhueza May 15 '15 at 16:42