-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, 2014 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, 2014 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, 2014 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, 2014 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, 2014 at 11:44

1 Answer 1

Reset to default
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 and acknowledge you have read our privacy policy.

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