0
$\begingroup$

I am doing problem 1.g. My Approach is to first create a NFA that accepts this string i.e. all strings having 110. Then converting it into DFA and then complementing it. I have the answer what should I get however my NFA to DFA conversion doesn't work. I don't know why. Can anyone guide me. Thanks. Here is my NFA. Note this is not full answer as there is complement left to be done. But I am stuck in between.

NFSM

Then I converted it into FSA

This is What I got

My Result

I know there is a mistake that there should be self loop of 1 on the AC state but from my above NFA, I am unable to obtain it. Is my NFA wrong? Or I have done some mistake in conversion.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

Your third state is wrong. From state (AB) on input 1, the next state is not (AC), it is (ABC). Think about it - if you are in state A -or- B, on 1 you can go from A to A, from A to B, or from B to C.

Improve this answer
$\endgroup$
3
$\begingroup$

I don't think you did the conversion correctly. You don't show your steps so I can't tell where you went wrong, but check your work again. If the NFA is in state A and it receives a 1, what states might it go to? If the NFA is in state C and it receives a 1, what states might it go to? So what state should the DFA (FSA) go to if it is in state AC and receives a 1?

There appear to be multiple errors in the conversion. For instance, the edge out of AB also looks incorrect.

Try applying the standard algorithm and running it by hand, one step at a time.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Yes. My bad, I totally made a mistake. The third state should be ABC. Thanks. $\endgroup$
    – Brij Raj Kishore
    Feb 22, 2018 at 3:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.