# Is this NFA correct for the language {w | w ends with an a and no a occurs between any occurrences of b}?

Language: {w | w ends with an a and no a occurs between any occurrences of b}

The NFA must have exactly 3 states.

-
This one looks okay; the language is $a^*b^*a^*a$. – Brian M. Scott Nov 7 '12 at 22:59
Thanks for confirming. – zeqof Nov 8 '12 at 7:16

## 1 Answer

It depends a little on what NFA are allowed. Your machine is OK (as Brian told you) but has two initial states. Not everyone likes that.

Alternatively, change the label from (0,a,1) into (0,b,1) and add an edge (0,a,2). Then only state 0 needs to be initial.

-
Oh I see. I didn't know one initial state was best practice. Thanks for your insight. – zeqof Nov 8 '12 at 7:17
This depends on the definition you are used to (or have to work with). If it is allowed, then please use it when it simplifies the solution. Another point is epsilon transitions (edges that do not read a symbol). I some books they are allowed in non-deterministic automata, in other approaches they are extra. – Hendrik Jan Nov 8 '12 at 10:40