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.


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 2

Are multiple completion states allowed?


2 Answers 2


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:

DFA accepting a^{+}b^{*}

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

  • $\begingroup$ Didn't consider the empty string, thanks for your help! $\endgroup$
    – Eogcloud
    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

  • $\begingroup$ (How do you intend the right arrows following the state designations interpreted?) $\endgroup$
    – greybeard
    Apr 24 at 8:23
  • $\begingroup$ 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. $\endgroup$
    – Kai
    Apr 24 at 13:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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