English subtitles

← 03xpsps-01 Fsm Optimization Solution

dummy description

Get Embed Code
3 Languages

Showing Revision 2 created 10/24/2012 by Amara Bot.

  1. In this problem, we have a bit of a challenge, and I've accordingly labeled it with
  2. 2 gold stars, but what we want to do here,
  3. is optimize a finite state machine.
  4. So to go through an example, let's say we have this finite state machine.
  5. There's 1 accepting state at state 1, and then we have these few others.
  6. If you quickly look at it and think about what's going on,
  7. once you take a path down the b to state 2,
  8. you can never get to the accepting state.
  9. From state 2, 3, or 4, there's no way to get to state 1.
  10. So any string that goes down this path is always going to fail.
  11. This state machine is equivalent to the one that doesn't include any of these states.
  12. So we can make it a lot simpler.
  13. Why would we want to do this?
  14. Well, if you haven't noticed we've been using a lot of regular expressions
  15. in building our web browser.
  16. Those regular expressions are represented as finite state machines,
  17. and that's how they're processed.
  18. In order to make our web browser faster, it turns out we want as small finite state machines
  19. as possible.
  20. So what we're going to do is write code.
  21. Given a definition of finite state machine like the that we have here,
  22. we're going to identify states that don't matter towards the execution,
  23. and we call those dead states and remove them from the definition,
  24. while maintaining the exact same language, while recognizing the exact same strings
  25. that our finite state machine did before.
  26. So how are we going to this? Let's come up with a plan.
  27. So here we have "The Plan."
  28. Step 1--Let's find the live states and the dead states.
  29. We're going to do this by just finding the live states and assuming everything else is dead.
  30. So how are we going to do that?
  31. Well, we're going to find all the states, and we can do that by iterating through our dictionary,
  32. and with each state, we're going to run nfsmaccepts,
  33. which is from homework 1, and it's a procedure that given a definition
  34. for a finite state machine, a starting state, and the accepting states,
  35. it sees if it's possible to get from that state to any accepting state--
  36. if it's possible to succeed from where we're at.
  37. So if I give this definition in state 3, it's going to tell me, no, we can't get to state 1
  38. or any accepting state for that matter.
  39. If I give a 1, it's going to say, yep, this is all good.
  40. So that's actually going to be your definition for live versus dead.
  41. It can actually find a live state versus a dead state, which is awesome.
  42. Step 2--We're going to create a new finite state machine that doesn't have any
  43. of the dead states.
  44. In order to make it a really good, kind of clean, definition, we have to take some care.
  45. We don't want to include any transitions that lead to dead states.
  46. We want to remove all of the dead states,
  47. and we also want to remove states that no longer point to any live states.
  48. So here I have a bunch of little subparts.
  49. We're going to go through each edge state, each entry in our dictionary.
  50. If the current state is dead, we're not going to copy it into our new finite state machine.
  51. Otherwise, we're going to go through all of the destinations it had in the original
  52. finite state machine and prepare to copy over any that are still alive.
  53. If there are none that are still alive, we're going to remove that edge completely.
  54. We're not going to copy it into a new one.
  55. Once we have repeated that process in every state edge thing in the graph,
  56. we're going to update our accepting state list accordingly.
  57. We don't want to have any accepting states that are dead.
  58. So let's go to the solution.
  59. One of the first things I did is I copied in nondeterministic finite state machine accepts
  60. directly from unit 1 homework.
  61. It hasn't changed a bit.
  62. Now I'm going to do my trimming of my finite state machine.
  63. So like I said in my outline, I'm going to find all the states,
  64. just so I have a record of them, and it doesn't really matter if I have duplicates.
  65. It might slow down the trimming a bit, but I'm doing this to save time
  66. when I'm running the execution, not for the trimming so much.
  67. For each state, if it's live, I can tell by running nfsmaccepts,
  68. and if it is live, I'm going to add it to a list of live states.
  69. Now I'm going to create a new dictionary of edges--my new representation,
  70. and go through all of the old ones to see if they're still live and update them accordingly.
  71. So for each edge in the old dictionary, if that state is live,
  72. then I'm going to calculate the new destinations, meaning I'm going to remove the destinations
  73. that are now dead.
  74. So if that destination is live, I'm going to append it to the list.
  75. But I only want to set this new edge to my new finite state machine dictionary
  76. if the destinations are not empty.
  77. There's really no point in having an edge that goes to nowhere,
  78. that goes to fail.
  79. We just kind of always assume that if the edge doesn't exist, then we're going to fail.
  80. Lastly, I want to update my accepting states to only those that are live.
  81. I'm going to return the tuple of the new edges and the new accepting states.
  82. And that's it.
  83. Look! It's true! So much true!
  84. True means good. It means meaning and greatness.