# Finite State Automata for recognising consecutive characters

I'm currently working on this question as part of some homework, it has me stumped.

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.

-
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

## 1 Answer

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.

-
Thanks for this, helped a lot! – Eogcloud Nov 17 '12 at 23:17