Return to Video

01-58 Nondet To Det

  • 0:00 - 0:02
    Let's do one more bit of practice
  • 0:02 - 0:06
    converting non-deterministic machines to deterministic ones.
  • 0:06 - 0:09
    Here I've written a non-deterministic machine.
  • 0:09 - 0:11
    It has ambiguity.
  • 0:11 - 0:14
    Right in state 1 there are 2 ways to go on a.
  • 0:14 - 0:16
    It also has epsilon transitions,
  • 0:16 - 0:20
    and I'll start making its deterministic equivalent down here.
  • 0:20 - 0:23
    Well, when we enter the non-deterministic machine,
  • 0:23 - 0:27
    we could only be in state 1, but after that we could see an a,
  • 0:27 - 0:31
    and if I see an a I could be in 2, 4,
  • 0:31 - 0:34
    or I could take the free epsilon transition to 5,
  • 0:34 - 0:38
    or I could keep going and take the free epsilon transition to 6.
  • 0:38 - 0:40
    I'll label my new state 2456
  • 0:40 - 0:42
    because it keeps track of everywhere that I could have my fingers
  • 0:42 - 0:45
    if I'm simulating this non-deterministic machine.
  • 0:45 - 0:48
    Now, should this state be an accepting state or not?
  • 0:48 - 0:52
    Well, remember that a finite state machine accepts if there's any path
  • 0:52 - 0:56
    to an accepting state, and 6 is one of our accepting states.
  • 0:56 - 0:59
    Because the original machine could accept a,
  • 0:59 - 1:03
    a, epsilon, epsilon, win, we want our new machine to also accept a.
  • 1:03 - 1:05
    A, win.
  • 1:05 - 1:10
    In my converted world, the state accepts if any of its corresponding
  • 1:10 - 1:13
    original states also accept.
  • 1:13 - 1:17
    Let's say that I'm in either 2, 4, 5, or 6 and I see a c.
  • 1:17 - 1:20
    If I'm in 2 and I see a c, I fall off the world.
  • 1:20 - 1:22
    If I'm in 4, fall off the world.
  • 1:22 - 1:24
    5, I go to 6, looking good.
  • 1:24 - 1:27
    6, fall off the world.
  • 1:27 - 1:31
    Here if I was in 2, 4, 5, or 6 and I see a c,
  • 1:31 - 1:36
    I end up just in state 6, and that's definitely an accepting state.
  • 1:36 - 1:39
    Now, there's some other ways to get out of 2, 4, 5, and 6,
  • 1:39 - 1:42
    and when we do, we might be in states 2 or 3.
  • 1:42 - 1:45
    Since 3 is an accepting state up there,
  • 1:45 - 1:48
    2 or 3 is an accepting state down here.
  • 1:48 - 1:52
    If I'm in 2 or 3, on a b from 2 I go to 3,
  • 1:52 - 1:57
    and c I'd fall off the world, so we'd end up in state 3.
  • 1:57 - 1:59
    If I'm in 2 or 3 and I see a c,
  • 1:59 - 2:02
    I must really have been in state 3, and I stay in state 3,
  • 2:02 - 2:07
    so either on b or c we end up in just state 3,
  • 2:07 - 2:09
    which is also an accepting state.
  • 2:09 - 2:13
    And if I'm in state 3, there's a self-loop back to state 3.
  • 2:13 - 2:17
    Now, I've filled out almost all of this deterministic equivalent.
  • 2:17 - 2:20
    But I forgot to label an edge.
  • 2:20 - 2:22
    Help me out.
  • 2:22 - 2:24
    As the quiz, what should the label for this edge be
  • 2:24 - 2:28
    so that this deterministic equivalent and this non-deterministic machine
  • 2:28 -
    accept exactly the same language?
Title:
01-58 Nondet To Det
Description:

more » « less
Video Language:
English
Team:
Udacity
Project:
CS262 - Programming Languages
Duration:
02:32
Amara Bot added a translation

English subtitles

Revisions