Finite state automata, multiple completion states? I'm currently studying for an exam for a course where some of the material covered included finite state automata, I've completed a question and I'm not sure about my answer.

Exercise

Explain what is meant by a Finite State Automaton (FSA) by drawing an FSA to recognise strings of the form $a^rb^s$, where $r\gt0$ and $s\ge0$ and with an alphabet of $\{a,b\}$, i.e., there must be at least one $a$, zero or more $b$'s and all occurrences of $a$ must precede any occurrence of $b$. Illustrate, how your FSA works given the following sample strings:
$\quad$(i) $abbb$
$\quad$(ii) $aaaa$
$\quad$(iii) $aba$

My Answer


Are multiple completion states allowed?
Your DFA is close, but not quite right. Note that the description requires the strings in the language to have at least one $a$, whereas your DFA will accept the empty string. The fix is simple of course:



And yes, having multiple accept states is fine (in fact, some languages require it).