0
$\begingroup$

I want to convert below NFA into DFA:

enter image description here

I prepared below tables and finally the NFA:

enter image description here

enter image description here

NFA

enter image description here

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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)$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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"? $\endgroup$
    – Mahesha999
    Commented May 15, 2015 at 15:05
  • $\begingroup$ 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. $\endgroup$
    – Klaus Draeger
    Commented May 15, 2015 at 16:28
  • $\begingroup$ 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. $\endgroup$
    – Renato Sanhueza
    Commented May 15, 2015 at 16:42

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.