English subtitles

← 01-51 Mis Msf Solution

Get Embed Code
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.