automatanfa

NFA for this specific design


I have this NFA bellow, and I feel that it has the regular expression (0+1)*00. But looking at it i also feel that I should add something to the RE for the transition q2->q0, but cant quite understand how to do it. Could anyone give me any tips? Thank you

enter image description here


Solution

  • If you want an NFA for (0 + 1)*00, your NFA works fine. Indeed, the transition from q2 to q0 is unnecessary; the NFA without that works as well. NFAs do not need to define all transitions and accept any string that has one accepted path through the NFA. Assuming q2 is an accepting state for you, it accepts any string in (0 + 1)*00 (self-loop on q0 for however many copies of (0 + 1) the Kleene closure is used to produce, and then go from q0 to q1 and q1 to q2) and only strings in (0 + 1)*00 (any string that gets from q0 to q2 and stays there must end with two 0s, which is the only requirement of strings in our language). In particular, it is legal for a NFA to "crash" on certain configurations; that just means that particular path through the NFA does not accept the string, but some other one might. If there are 10^1000000 paths through an NFA and all but one crashes or rejects, and just one leads to an accepting state, that string is in the language of the NFA.