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 working on this question as part of some homework, it has me stumped.

FSA Question

I'm familiar with finite state automata (FSA), I know how they work and I've read everything I can find on Google, but nothing's helped me come any closer to a solution.

If I don't know the length of the input string, or I'm not searching for a particular pattern, how can I design a machine that will always land on the final state?

I've tried drawing some, but that always end up being a little off.

share|cite|improve this question
A.Schulz's answer gives you pretty much everything, but from the conceptual level, it may be worth recognising that you are looking for a particular pattern - $bb$. The difference is that you want to reject when you find it, rather than accept (and if you haven't found it, then everything is still okay). – Luke Mathieson Nov 17 '12 at 9:05
Thank you for your help, I got it! – Eogcloud Nov 17 '12 at 23:16
up vote 2 down vote accepted

The FSA should have three states:

  • $q_a$ represents: last character was not a b, and no bb yet
  • $q_b$ represents: last character was a b, and no bb yet
  • $q_{bb}$ represents: there was already a bb

Clearly, you start with $q_a$ and you accept in $q_a$ and $q_b$. Now try to figure out how to connect the states.

share|cite|improve this answer
Thanks for this, helped a lot! – Eogcloud Nov 17 '12 at 23:17

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.