01-57 Nondeterminism

• 0:00 - 0:04
These easy-to-write FSMs that we've been using
• 0:04 - 0:07
that involve epsilon transitions or ambiguity--
• 0:07 - 0:11
remember, ambiguity means that I can go to 2 different places on the same input--
• 0:11 - 0:16
are formerly known as non-deterministic finite state machines.
• 0:16 - 0:19
Non-deterministic here just means that you may not know exactly
• 0:19 - 0:21
where to go or where to put your finger.
• 0:21 - 0:24
It's not lock-step. You have choices.
• 0:24 - 0:26
You have freedom.
• 0:26 - 0:29
A lock-step FSM with no epsilon transitions
• 0:29 - 0:34
and no ambiguity by contrast is called a deterministic finite state machine.
• 0:34 - 0:36
Everything is determined from the start.
• 0:36 - 0:38
Given the finite state machine and the input, you always know
• 0:38 - 0:40
exactly what will happen.
• 0:40 - 0:43
Our finite state machine simulation procedure can handle
• 0:43 - 0:46
deterministic finite state machines.
• 0:46 - 0:49
That makes them really useful for implementing regular expressions
• 0:49 - 0:51
under the hood.
• 0:51 - 0:55
Let me just show you an example of this non-determinism just to drive it home.
• 0:55 - 0:57
Suppose we were back here in this previous finite state machine,
• 0:57 - 1:00
but now the input is 1-23.
• 1:00 - 1:02
Where are we?
• 1:02 - 1:05
We started here, and on a 1 we went here,
• 1:05 - 1:08
and then I guess if we're supposed to stay alive and there's a hyphen,
• 1:08 - 1:11
we must have gone here and taken the hyphen.
• 1:11 - 1:14
And now there's a 2, but now this is really not obvious.
• 1:14 - 1:17
I could stay here on this self-loop for a 3,
• 1:17 - 1:20
or I could have gone back on this free epsilon transition
• 1:20 - 1:25
and done the self-loop here on a 3, so I could be in state 2 or state 5.
• 1:25 - 1:28
Since there isn't one single answer for where I could be,
• 1:28 - 1:30
this is non-deterministic.
• 1:30 - 1:34
As a bit of a fun aside, this notion of determinism
• 1:34 - 1:39
or non-determinism can be related to the question of free will in philosophy.
• 1:39 - 1:42
Can we actually make independent choices?
• 1:42 - 1:45
Or is everything preordained by the current state of the world
• 1:45 - 1:51
and forces acting on it, like a lock-step game of billiards or snooker or pool?
• 1:51 - 1:53
Some philosophers will approach this by suggesting that we have
• 1:53 - 1:57
the illusion of free will--that's a disconcerting thought--
• 1:57 - 2:00
which is handy for describing subjective experience.
• 2:00 - 2:02
We certainly often feel like we have free will.
• 2:02 - 2:05
Regardless of what's going on in the real world,
• 2:05 - 2:07
we're going to see that something similar holds
• 2:07 - 2:09
for finite state machines.
• 2:09 - 2:12
Although non-deterministic finite state machines look like they have
• 2:12 - 2:14
much more power and much more freedom,
• 2:14 - 2:17
anything that could be done with them could also be done
• 2:17 - 2:19
in our deterministic billiard ball world.
• 2:19 - 2:23
In fact, you can watch me suck free will out of this world right now.
• 2:23 - 2:26
Every non-deterministic finite state machine
• 2:26 - 2:29
has a corresponding deterministic finite state machine
• 2:29 - 2:33
that accepts exactly the same strings.
• 2:33 - 2:37
Non-deterministic finite state machines are not any more powerful
• 2:37 - 2:39
than deterministic finite state machines.
• 2:39 - 2:42
They're just more convenient.
• 2:42 - 2:44
It's easier to write them down.
• 2:44 - 2:46
Let's see an example of this extraordinary claim.
• 2:46 - 2:48
Suppose we have this regular expression.
• 2:48 - 2:51
There are only 2 strings in the language of this regular expression,
• 2:51 - 2:55
but here I've drawn out a very elaborate finite state machine for it
• 2:55 - 2:57
that has epsilon transitions coming out the wazoo.
• 2:57 - 3:00
This is very non-deterministic.
• 3:00 - 3:03
We definitely need to see an a, but then here these 2 epsilon transitions
• 3:03 - 3:05
represent the explicit choice.
• 3:05 - 3:08
Do I do the b, or do I skip over it?
• 3:08 - 3:10
On the top road, we need to see the b.
• 3:10 - 3:13
On the bottom road, we skip entirely past it.
• 3:13 - 3:15
And then in any event, we need to see the c.
• 3:15 - 3:19
I'm now going to write a deterministic finite state machine
• 3:19 - 3:22
that does exactly the same thing, and I'm going to hint at
• 3:22 - 3:24
how this conversion works.
• 3:24 - 3:26
We'll see this again in just a minute.
• 3:26 - 3:29
After I see an a, I could be in 2,
• 3:29 - 3:31
or I could take the epsilon to 3.
• 3:31 - 3:33
I could have taken the epsilon down here to 6
• 3:33 - 3:36
or all the way over to 4, so there are 4 places
• 3:36 - 3:38
I could be in.
• 3:38 - 3:40
That's a lot of fingers.
• 3:40 - 3:44
I'll just record all of them as the name for my new state, 2364.
• 3:44 - 3:49
From here, if I see a b and I survive--remember, finite state machines work
• 3:49 - 3:54
if there's any path that gets to the end--it must have been that I was in state 3,
• 3:54 - 3:57
at which point now I'm just in state 4.
• 3:57 - 4:03
By contrast, if I was back here and I saw a c,
• 4:03 - 4:06
it must have been that I was in state 4, and now I'm in state 5.
• 4:06 - 4:10
And then finally, if I'm in state 4 and I see a c,
• 4:10 - 4:13
I end up here, so this deterministic finite state machine
• 4:13 - 4:17
accepts the same language as the one above.
• 4:17 - 4:20
The 2 strings, a, b, c, and a, c
• 4:20 - 4:23
are both in it, but it does not have
• 4:23 - 4:25
epsilon transitions or ambiguity.
• 4:25 - 4:29
In any particular node, there are never 2 edges going out labeled a,
• 4:29 - 4:31
and there are never epsilon transitions.
• 4:31 - 4:34
Let's see another example of how this works.
• 4:34 - 4:37
Again, I'm going to build a deterministic machine
• 4:37 - 4:40
where every state in the deterministic machine
• 4:40 - 4:44
corresponds to a set of states
• 4:44 - 4:46
in the non-deterministic one.
• 4:46 - 4:50
Again, to restate that, you give me a non-deterministic machine,
• 4:50 - 4:53
I'm going to build you a deterministic machine d
• 4:53 - 4:57
that accepts the same language, and the way I'll do it is
• 4:57 - 5:01
every state in d is going to correspond to a set of states
• 5:01 -
in the non-deterministic machine you gave me.
Cím:
01-57 Nondeterminism
Leírás:

more » « less
Video Language:
English
Team:
Udacity
Projekt:
CS262 - Programming Languages
Duration:
05:05