1
$\begingroup$

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.

|cite|improve this question|||||
$\endgroup$
  • 1
    $\begingroup$ 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). $\endgroup$ – Luke Mathieson Nov 17 '12 at 9:05
2
$\begingroup$

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.

|cite|improve this answer|||||
$\endgroup$

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.