## ← 01-51 Mis Msf Solution

• 1 Follower
• 26 Lines

### Get Embed Code x Embed video Use the following code to embed this video. See our usage guide for more details on embedding. Paste this in your document somewhere (closest to the closing body tag is preferable): ```<script type="text/javascript" src='https://amara.org/embedder-iframe'></script> ``` Paste this inside your HTML body, where you want to include the widget: ```<div class="amara-embed" data-url="http://www.youtube.com/watch?v=-rCexC2MM7U" data-team="udacity"></div> ``` 5 Languages

Showing Revision 1 created 04/24/2012 by Amara Bot.

1. As always, I find the easiest way to answer such a question
2. is to draw the finite-state machine.
3. We come in in state 1, and on a we go to state 2.
4. And on b we go to state 3,
5. and then from state 2 on c
6. we go to 4, and state 3 on d we go to 5,
7. and 5 on e goes back to 2, and 5 on f
8. goes to state 6, and 5 on g
9. goes all the way back here to 1, and our only accepting state is 6.
10. Well, how can we get to state 6?
11. If we go up here to the right,
12. this is like the place of no return.
13. We go here, and then there's no way to ever get back down or get to 6,
14. so we don't want to go to 4.
15. We don't want to get to 2.
16. How about instead if we go 1, 3, 5, 6 or b, d, f?
17. But now I need to give another string
18. that's different but that's also accepted.
19. One way to do that would be to take this
20. go to start back loop here, pass go, start again.
21. 1, 3, 5, 1, 3, 5, 6.
22. So b, d, g, b, d, f.
23. Those are 2 strings that are both accepted but that are different.
24. And if you are feeling exotic, you could actually have gone around these loops more times.
25. You can add b, d, g, b, d, g, b, d, g at the beginning as often as you'd like
26. and make longer and longer strings.