Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.


My Answer

Are multiple completion states allowed?

share|cite|improve this question
I suggest writing down the questions from the images to the question itself here. This is if/when the links break, the question here becomes meaningless. – Juho Nov 27 '12 at 1:53
up vote 3 down vote accepted

Your DFA is a 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).

share|cite|improve this answer
Didn't consider the empty string, thanks for your help! – Eogcloud Nov 27 '12 at 2:50

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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