[Script Info]
Title:
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.00,0:00:02.00,Default,,0000,0000,0000,,Let's do one more bit of practice
Dialogue: 0,0:00:02.00,0:00:06.00,Default,,0000,0000,0000,,converting non-deterministic machines to deterministic ones.
Dialogue: 0,0:00:06.00,0:00:09.00,Default,,0000,0000,0000,,Here I've written a non-deterministic machine.
Dialogue: 0,0:00:09.00,0:00:11.00,Default,,0000,0000,0000,,It has ambiguity.
Dialogue: 0,0:00:11.00,0:00:14.00,Default,,0000,0000,0000,,Right in state 1 there are 2 ways to go on a.
Dialogue: 0,0:00:14.00,0:00:16.00,Default,,0000,0000,0000,,It also has epsilon transitions,
Dialogue: 0,0:00:16.00,0:00:20.00,Default,,0000,0000,0000,,and I'll start making its deterministic equivalent down here.
Dialogue: 0,0:00:20.00,0:00:23.00,Default,,0000,0000,0000,,Well, when we enter the non-deterministic machine,
Dialogue: 0,0:00:23.00,0:00:27.00,Default,,0000,0000,0000,,we could only be in state 1, but after that we could see an a,
Dialogue: 0,0:00:27.00,0:00:31.00,Default,,0000,0000,0000,,and if I see an a I could be in 2, 4,
Dialogue: 0,0:00:31.00,0:00:34.00,Default,,0000,0000,0000,,or I could take the free epsilon transition to 5,
Dialogue: 0,0:00:34.00,0:00:38.00,Default,,0000,0000,0000,,or I could keep going and take the free epsilon transition to 6.
Dialogue: 0,0:00:38.00,0:00:40.00,Default,,0000,0000,0000,,I'll label my new state 2456
Dialogue: 0,0:00:40.00,0:00:42.00,Default,,0000,0000,0000,,because it keeps track of everywhere that I could have my fingers
Dialogue: 0,0:00:42.00,0:00:45.00,Default,,0000,0000,0000,,if I'm simulating this non-deterministic machine.
Dialogue: 0,0:00:45.00,0:00:48.00,Default,,0000,0000,0000,,Now, should this state be an accepting state or not?
Dialogue: 0,0:00:48.00,0:00:52.00,Default,,0000,0000,0000,,Well, remember that a finite state machine accepts if there's any path
Dialogue: 0,0:00:52.00,0:00:56.00,Default,,0000,0000,0000,,to an accepting state, and 6 is one of our accepting states.
Dialogue: 0,0:00:56.00,0:00:59.00,Default,,0000,0000,0000,,Because the original machine could accept a,
Dialogue: 0,0:00:59.00,0:01:03.00,Default,,0000,0000,0000,,a, epsilon, epsilon, win, we want our new machine to also accept a.
Dialogue: 0,0:01:03.00,0:01:05.00,Default,,0000,0000,0000,,A, win.
Dialogue: 0,0:01:05.00,0:01:10.00,Default,,0000,0000,0000,,In my converted world, the state accepts if any of its corresponding
Dialogue: 0,0:01:10.00,0:01:13.00,Default,,0000,0000,0000,,original states also accept.
Dialogue: 0,0:01:13.00,0:01:17.00,Default,,0000,0000,0000,,Let's say that I'm in either 2, 4, 5, or 6 and I see a c.
Dialogue: 0,0:01:17.00,0:01:20.00,Default,,0000,0000,0000,,If I'm in 2 and I see a c, I fall off the world.
Dialogue: 0,0:01:20.00,0:01:22.00,Default,,0000,0000,0000,,If I'm in 4, fall off the world.
Dialogue: 0,0:01:22.00,0:01:24.00,Default,,0000,0000,0000,,5, I go to 6, looking good.
Dialogue: 0,0:01:24.00,0:01:27.00,Default,,0000,0000,0000,,6, fall off the world.
Dialogue: 0,0:01:27.00,0:01:31.00,Default,,0000,0000,0000,,Here if I was in 2, 4, 5, or 6 and I see a c,
Dialogue: 0,0:01:31.00,0:01:36.00,Default,,0000,0000,0000,,I end up just in state 6, and that's definitely an accepting state.
Dialogue: 0,0:01:36.00,0:01:39.00,Default,,0000,0000,0000,,Now, there's some other ways to get out of 2, 4, 5, and 6,
Dialogue: 0,0:01:39.00,0:01:42.00,Default,,0000,0000,0000,,and when we do, we might be in states 2 or 3.
Dialogue: 0,0:01:42.00,0:01:45.00,Default,,0000,0000,0000,,Since 3 is an accepting state up there,
Dialogue: 0,0:01:45.00,0:01:48.00,Default,,0000,0000,0000,,2 or 3 is an accepting state down here.
Dialogue: 0,0:01:48.00,0:01:52.00,Default,,0000,0000,0000,,If I'm in 2 or 3, on a b from 2 I go to 3,
Dialogue: 0,0:01:52.00,0:01:57.00,Default,,0000,0000,0000,,and c I'd fall off the world, so we'd end up in state 3.
Dialogue: 0,0:01:57.00,0:01:59.00,Default,,0000,0000,0000,,If I'm in 2 or 3 and I see a c,
Dialogue: 0,0:01:59.00,0:02:02.00,Default,,0000,0000,0000,,I must really have been in state 3, and I stay in state 3,
Dialogue: 0,0:02:02.00,0:02:07.00,Default,,0000,0000,0000,,so either on b or c we end up in just state 3,
Dialogue: 0,0:02:07.00,0:02:09.00,Default,,0000,0000,0000,,which is also an accepting state.
Dialogue: 0,0:02:09.00,0:02:13.00,Default,,0000,0000,0000,,And if I'm in state 3, there's a self-loop back to state 3.
Dialogue: 0,0:02:13.00,0:02:17.00,Default,,0000,0000,0000,,Now, I've filled out almost all of this deterministic equivalent.
Dialogue: 0,0:02:17.00,0:02:20.00,Default,,0000,0000,0000,,But I forgot to label an edge.
Dialogue: 0,0:02:20.00,0:02:22.00,Default,,0000,0000,0000,,Help me out.
Dialogue: 0,0:02:22.00,0:02:24.00,Default,,0000,0000,0000,,As the quiz, what should the label for this edge be
Dialogue: 0,0:02:24.00,0:02:28.00,Default,,0000,0000,0000,,so that this deterministic equivalent and this non-deterministic machine
Dialogue: 0,0:02:28.00,9:59:59.99,Default,,0000,0000,0000,,accept exactly the same language?