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?


1 Answer 1


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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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