Return to Video

03xpsps-01 Fsm Optimization Solution

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

dummy description

more » « less
Video Language:
English
Team:
Udacity
Project:
CS262 - Programming Languages
Duration:
05:24
Amara Bot edited English subtitles for 03xpsps-01 Fsm Optimization Solution
Gundega added a translation

English subtitles

Revisions Compare revisions