# 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$$

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).

• Didn't consider the empty string, thanks for your help! Nov 27, 2012 at 2:50

In my opinion the answer suggested has redundant states. It can be simply made with 2 states:
q0 → if $$a$$ → q1 (count one $$a$$ in this way) if $$b$$ → q0 (stay on initial state)
q1 → if $$a$$,$$b$$ stay on q1 take as many $$a$$ or $$b$$ as the string has until string ends
q1 is accept state
q0 is initial state

• (How do you intend the right arrows following the state designations interpreted?) Apr 24 at 8:23
• This is just wrong. The index (as per Myhill-Nerode) of the language $a^+b^*$ is greater than $2$ which implies that the smallest DFA recognising the language must have more than $2$ states.
– Kai
Apr 24 at 13:08