﻿[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?