-1
$\begingroup$

I've been solving some exercises recently and it appears my answer was wrong for this particular example. The task is to convert this NFA into a DFA:

enter image description here

My attempt is this:

enter image description here

Now the tool I'm using (Exorciser) says that there is still nondeterminism in the automaton (even though it's equivalent to the original).

I don't see it; where is the mistake?

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ The non-determinism comes from the state {q0, q2} because on input b, there are two transitions i.e. the self loop on {q0, q2} itself and second the transition to state q2. So when the NFA reaches the state {q0, q2} - it has two options of taking a transition and has to <b>non-deterministically</b> decide on which state to take a transition. $\endgroup$ – Abdussami Tayyab Aug 13 '14 at 11:09
  • 2
    $\begingroup$ Similarly, you can figure out where else your mistake was by following this concept, I recommend following a Powerset Construction algorithm by which mistakes are minimal. $\endgroup$ – Abdussami Tayyab Aug 13 '14 at 11:10
  • 2
    $\begingroup$ This question appears to be unsuited for this site because questions of the form: "This is the exercise problem, this is my solution. Please grade!" are not interesting for anyone but you. Please see this related meta discussion. If you want to ask a specific question about a specific part of your attempt, please edit the question accordingly and it may be reopened. Otherwise, you might want to visit Computer Science Chat and get some feedback there. (Also, much relevant information is solely avaible in the picture, i.e. what the issue is.) $\endgroup$ – Raphael♦ Aug 13 '14 at 11:29
  • $\begingroup$ I edited your question into shape; this is the minimal effort we usually expect you to expend. $\endgroup$ – Raphael♦ Aug 13 '14 at 11:43
  • 2
    $\begingroup$ As for your question: there are several algorithms for this kind of conversion. Which did you employ? Check your steps -- you made a mistake somewhere. Finding the non-determinism is easy: just look for a node with two outgoing edges that share a label. So I'm not quite sure what kind of answer you are expecting here. $\endgroup$ – Raphael♦ Aug 13 '14 at 11:44
3
$\begingroup$

The non-determinism comes from the state {q0, q2} because on input b, there are two transitions i.e. the self loop on {q0, q2} itself and second the transition to state q2. So when the NFA reaches the state {q0, q2} - it has two options of taking a transition and has to non-deterministically decide which state to take a transition to.

Following this mini-method I told above, you can figure out where you are wrong.

However, for conversion of NFA's to DFA's, I recommend following a Powerset Construction algorithm by which mistakes are minimal.

Improve this answer
$\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.