1
$\begingroup$

I was working through an NFA to DFA conversion tutorial: where I'm converting the following NFA to a DFA:
NFA to a DFA:
I used lazy subset construction which I'm sure the tutorial did as well because we had the same transition table of:

delta      |  0        |  1       |
===========+===========+==========+
{a}        |{a,b,c,d,e}|{d,e}
{a,b,c,d,e}|{a,b,c,d,e}|{b,d,e}   
{d,e}      |{e}        |{∅}       
{b,d,e}    |{c,e}      |{e}       
{e}        |{∅}        |{∅}       
{c,e}      |{∅}        |{b}       
{b}        |{c}        |{e}
{c}        |{∅}        |{b}

However, there state diagram for the resulting DFA is this:
Resulting DFA

I'm confused as to why the set {b,d,e} isn't being labeled as an accepting state.

Also, I don't know if I'm allowed to ask this but if there is a place with more NFA to DFA converting practice I'd love to know, right now I'm just using any old study guide I can find on google.

$\endgroup$
1
$\begingroup$

You're right, {b, d, e} should be a final state. Otherwise the DFA would reject 0001 while the "equivalent" NFA accepts it.

$\endgroup$
  • $\begingroup$ That makes me feel better about my understanding, thanks $\endgroup$ – Austin Mauldin Feb 7 '17 at 20:43

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.