Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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|improve this question
1  
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
add comment

1 Answer

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|improve this answer
    
Thanks for this, helped a lot! –  Eogcloud Nov 17 '12 at 23:17
add comment

Your Answer

 
discard

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.