Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

The NFA must have exactly 3 states.

enter image description here

share|cite|improve this question
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
up vote 1 down vote accepted

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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