## 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
• 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
• 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

• Amara Bot
• Gundega