2
$\begingroup$

I am trying to learn how to construct an NFA state diagram.

$$M = \{q0, q1, q2\}, \{a,b\}, \delta, q0 , \{q2\}$$

$δ(q0,a) = q0; \delta(q0,b) = {q0,q1}; \delta(q1,a)= {q0, q2}; \delta(q1,b) = {q1}; \delta(q2,b) = {q1}$

From the above notation, I drew the state diagram below. Is this diagram correct? NFA state diagram

In state $q1$ I don't understand how $a$ can transition to state $q0$ OR to state $q2$. How can the string $ba$ be accepted but also not accepted, depending on which path the NFA takes? Can you help me understand.

$\endgroup$
5
  • 5
    $\begingroup$ possible duplicate: cs.stackexchange.com/q/2016/755. I think the answers there will tell you how to do the conversion. If you think there is some reason this question is not answered by the answers there, please edit the question to identify why not and to focus this question specifically on the aspect that's not covered there. Your questions in the last paragraph don't seem to have anything to do with conversion to a regexp, so if that's really what you want to know, I suggest you edit the question to remove everything about regexps and conversion to regexp. $\endgroup$
    – D.W.
    Oct 14, 2015 at 3:35
  • 1
    $\begingroup$ As far as your questions in the last paragraph, what self-study have you done? You're basically asking "I don't understand non-determinism". That's explained in many standard textbooks on automata theory (as well as online, e.g., Wikipedia). There would be little point in us repeating that material. What materials have you read, and what specifically don't you understand? $\endgroup$
    – D.W.
    Oct 14, 2015 at 3:36
  • $\begingroup$ @astra , are state q0 and q2 both final states ? $\endgroup$ Oct 15, 2015 at 7:03
  • $\begingroup$ No, only q2 is a final state. I updated the expression so that it is clear. $\endgroup$
    – alig227
    Oct 15, 2015 at 13:59
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ Oct 15, 2015 at 23:00

0