Return to Video

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
Amara Bot hozzáadott egy fordítást

English subtitles

Felülvizsgálatok