0
$\begingroup$

I have converted nfa to dfa. But when I checked with some examples, it looks like it is wrong.

This is the full question.
Convert the nfa defined by
δ(q0, a) = {q0, q1}
δ(q1, b) = {q1, q2}
δ(q2, a) = {q2}
δ(q1, λ) = {q1, q2}
with initial state q0 and final state q2 into an equivalent dfa.

First, I made a table.

             a          b
ɸ            ɸ          ɸ
{q0}         {q0,q1}    ɸ
{q1}         ɸ          {q1,q2}
{q2}         {q2}       ɸ
{q0,q1}      {q0,q1}    {q1,q2}
{q1,q2}      {q2}       {q1,q2}
{q0,q2}      {q0,q1,q2} ɸ
{q0,q1,q2}   {q0,q1,q2} {q1,q2}

Finally, I have drawn dfa according to table above. enter image description here The bold line is accepting state.

Thanks for your help/

$\endgroup$
7
  • $\begingroup$ The sample input strings you used to disprove your transformation would be helpful in figuring out where your error is. Otherwise I'd need to re-solve the problem myself from scratch. $\endgroup$ – Ertai87 Apr 16 '20 at 17:59
  • $\begingroup$ @Ertai87 One disprove was that when I did a->λ, it is q2 in nfa. However, in my dfa it does not go. $\endgroup$ – Sungtaek Yang Apr 16 '20 at 18:03
  • $\begingroup$ Is \lambda a character in your language? I don't see it in your transition chart or in your graphical diagram. I'm not quite sure what \lambda represents. $\endgroup$ – Ertai87 Apr 16 '20 at 18:05
  • $\begingroup$ @Ertai87 lambda is not a character. It's just a null thing $\endgroup$ – Sungtaek Yang Apr 16 '20 at 18:07
  • $\begingroup$ Transitioning on no input fundamentally violates the concept of a Finite State Machine (FSM). You can have a "null character" (a character which is defined to semantically represent "null input") which is acceptable, but then that character is still a character in the language. Is that what \lambda is? If so, then you need to include \lambda in your transition table just like a and b. $\endgroup$ – Ertai87 Apr 16 '20 at 18:11
1
$\begingroup$

It looks like you have 3 symbols in your language: a, b, and \lambda. But your transition table only has the symbols a and b. You need to add \lambda to your transition table and integrate that into your diagram. That should help some.

$\endgroup$

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.