1
$\begingroup$

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

  • 0
    This one looks okay; the language is $a^*b^*a^*a$.2012-11-07

1 Answers 1

1

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.

  • 0
    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.2012-11-08