1 00:00:03,780 --> 00:00:08,652 Welcome back. In this video, we're going to talk about converting nondeterministic 2 00:00:08,652 --> 00:00:16,860 finite automata into deterministic finite automata. Here again is our little diagram 3 00:00:16,860 --> 00:00:22,041 of the pipeline of a lexical analyzer, how one is constructed. So beginning with the 4 00:00:22,041 --> 00:00:26,724 lexical specification, we write our regular expressions. Last time we talked 5 00:00:26,724 --> 00:00:31,655 about the step, the conversion of regular expressions and the non-deterministic 6 00:00:31,655 --> 00:00:36,837 finite automata and this time we're going to talk about this step. And as you might 7 00:00:36,837 --> 00:00:41,831 guess in the final video in the series we'll talk about the final step which is 8 00:00:41,831 --> 00:00:47,868 the implementation of DFA's. So here's the Nondeterministic Finite Automata and we 9 00:00:47,868 --> 00:00:52,824 finished up with last time. And, the first thing we're gonna discuss today is an 10 00:00:52,824 --> 00:00:57,572 important idea called the Epsilon Closure of a state. And the basic idea of the 11 00:00:57,572 --> 00:01:02,566 epsilon culture is that I pick the states. And it could a set of states but we'll 12 00:01:02,566 --> 00:01:08,373 just do it for a single state. And then I look at all the states that I can reach by 13 00:01:08,373 --> 00:01:13,973 following only epsilon moves. And so b is the state that we're starting with so b 14 00:01:13,973 --> 00:01:19,366 would be included in the set and then there's an epsilon move to c. So c would 15 00:01:19,366 --> 00:01:25,174 be included in the set and there's another epsilon move to d so d would be included 16 00:01:25,174 --> 00:01:30,705 in the set. So we would say, the epsilon closure of b is = the set b c d. And let's 17 00:01:30,705 --> 00:01:37,495 do one more as an example. Want to take the epsilon closure of g. And when we 18 00:01:37,495 --> 00:01:44,367 switch colors up to this one, I'll erase that and to this one in pink, Our 19 00:01:44,367 --> 00:01:49,512 purple-ish pink. So the epsilon closure of g, we always have to follow all the 20 00:01:49,512 --> 00:01:54,857 epsilon transitions out of g. So, h would be in the epsilon closure of g but it's 21 00:01:54,857 --> 00:02:00,069 not just single epsilon move. This is recursive. So any number of epsilon moves 22 00:02:00,069 --> 00:02:05,415 that I can take, all of those states are included in the epsilon closure of g. So, 23 00:02:05,415 --> 00:02:11,894 in fact, i would also be included. A would be included and b and c and d will also be 24 00:02:11,894 --> 00:02:18,226 included And now, if I look at all of these states that have been colored in the 25 00:02:18,226 --> 00:02:25,774 light purple color. I can see that I can't reach any new states from those states 26 00:02:25,774 --> 00:02:33,475 using only epsilon moves and so the epsilon closure of g would be equal to and 27 00:02:33,475 --> 00:02:44,609 [inaudible] out here it's a, b, c, d. Ghi. Okay. So that is the epsilon closure of a 28 00:02:44,609 --> 00:02:51,973 state. Recall from the last video that an NFA maybe in many states any given point 29 00:02:51,973 --> 00:02:57,125 in time that is because of the choices it can make for a given input and NFA may 30 00:02:57,125 --> 00:03:02,150 reach multiple different states. And the question we want to address now is how 31 00:03:02,150 --> 00:03:07,174 many different states can it be in? Well if a non-deterministic automaton has n 32 00:03:07,174 --> 00:03:13,055 states. And it winds up in some subset of those states as how big can that subset b 33 00:03:13,055 --> 00:03:18,991 will clearly the cardinality of that said has to be less than or equal to n. So the 34 00:03:18,991 --> 00:03:24,641 NFA can get into a most and different states. Now instead, I want to know the 35 00:03:24,641 --> 00:03:30,649 number of different subsets, well how many different subsets are there of any things. 36 00:03:30,649 --> 00:03:36,140 Well that means there are two to the n - one possible subsets of n states. And 37 00:03:36,140 --> 00:03:41,683 there's something very interesting about this number. First of all it's a very big 38 00:03:41,683 --> 00:03:46,551 number so clearly the NFA can get into lots of different configurations 39 00:03:46,551 --> 00:03:52,095 particularly one it has a lot of different states but the important thing is that 40 00:03:52,095 --> 00:04:03,528 this is a finite set of possible configurations. And this is going to give 41 00:04:03,528 --> 00:04:09,297 us the seed of the idea. For converting an NFA into a DFA or Deterministic Automata 42 00:04:09,297 --> 00:04:15,103 because all we have to be able to do to convert a Nondeterministic Automata into 43 00:04:15,103 --> 00:04:20,375 Deterministic Automata is come up with a way for the Deterministic Automata to 44 00:04:20,375 --> 00:04:25,380 simulate for the [inaudible] of the Nondeterministic Automata and the fact 45 00:04:25,380 --> 00:04:29,985 that the Nondeterministic Automata can only get into a finite set of 46 00:04:29,985 --> 00:04:35,191 configurations even that configurations is very large, is exactly what we will 47 00:04:35,191 --> 00:04:41,465 exploit in the construction. Now we're ready to give the construction showing how 48 00:04:41,465 --> 00:04:46,510 to map an arbitrary nondeterministic finite automaton to an equivalent 49 00:04:46,510 --> 00:04:51,981 deterministic finite automaton. So let's begin by saying what's in our NFA. So, 50 00:04:51,981 --> 00:04:58,024 we'll have a set of states, Which we'll call s and these are the states of the 51 00:04:58,024 --> 00:05:04,035 Nondeterministic machine. There's a star t state, a little s which is one of the 52 00:05:04,035 --> 00:05:09,836 states and there is a set of final states F. And then we also have to give the 53 00:05:09,836 --> 00:05:15,021 transition function and I want to write out the state transition function. I want 54 00:05:15,021 --> 00:05:20,141 to use the state transition function to define a, a operator that we're going to 55 00:05:20,141 --> 00:05:27,244 find handy for defining our DFA. So I'd say that a applied to a set of states so x 56 00:05:27,244 --> 00:05:34,492 here is a set of states and a is a character in the input language. So, a and 57 00:05:34,492 --> 00:05:42,502 x is = those states y such that there is some x little x here, single state in the 58 00:05:42,502 --> 00:05:49,927 set of states such that there's a transition from x to y on input a. Okay. 59 00:05:49,927 --> 00:05:56,178 So this is just a way of saying I've given the transition function at this set level. 60 00:05:56,178 --> 00:06:02,061 It says for a given set of state x, show me all the states that you can reach on 61 00:06:02,061 --> 00:06:22,288 input a. Alright. So now we're ready to define our DFA. So what will the DFA be? 62 00:06:22,288 --> 00:06:27,769 Well, it's gonna have to have all of these things. It's gonna have to have, perhaps 63 00:06:27,769 --> 00:06:33,250 where the states are? What are the start state is? What's the final states are and 64 00:06:33,250 --> 00:06:38,393 what's the transition function is? So let's begin with the set of states. The 65 00:06:38,393 --> 00:06:45,387 states will be the subsets Of s. So the states of the DFA will be all possible 66 00:06:45,387 --> 00:06:51,701 subsets of the states of the NFA so there will be one state of DFA for each subset 67 00:06:51,701 --> 00:06:57,482 of possible, each possible subset of states of the NFA. And of course this is 68 00:06:57,482 --> 00:07:03,720 potentially a very big number but it's still finite and so we can use that set 69 00:07:03,720 --> 00:07:10,033 of, of subsets of states as the states based of the Deterministic machine So, now 70 00:07:10,033 --> 00:07:16,040 what's the start state of the DFA. Well that's going to be the epsilon closure. 71 00:07:57,110 --> 00:08:03,410 Now one of the set of final states, Well, so the final states will be consist of 72 00:08:03,410 --> 00:08:09,631 those state x and every member of the states of the DFA are sets of states of 73 00:08:09,631 --> 00:08:16,170 the NFA. So that x is a set and is can be every x such that x intersected with the 74 00:08:16,170 --> 00:08:57,511 set of final states of the NFA is not empty. And finally we need to define the 75 00:08:57,511 --> 00:09:03,691 transition function. And do we do that? Well, we, we need to say that for a given 76 00:09:03,691 --> 00:09:10,346 state x and another state y, when is there a transition between them on some input a. 77 00:09:10,346 --> 00:09:17,319 Well that, there will be such a transition under that conditions and well let's write 78 00:09:17,319 --> 00:09:23,278 them out. So, remember we're in state x. And what do we need to know? Well we need 79 00:09:23,278 --> 00:09:28,959 to know, the set of states that we can reach on input A, and we'll be justifying 80 00:09:28,959 --> 00:09:34,497 that that's A of X, and then once we've gotten to where these, once we've seen 81 00:09:34,497 --> 00:09:40,609 where we can go from the set of states X of input A. There's also a possibility of 82 00:09:40,609 --> 00:09:45,284 making [inaudible] after that so furthermore we have to take the 83 00:09:45,284 --> 00:09:52,101 [inaudible] closer of that set of states, okay? And So we'll say that there's a 84 00:09:52,101 --> 00:10:00,124 transition from x to y if y is equal to this set of states. Alright, And notice 85 00:10:00,124 --> 00:10:05,582 that there's only one such set of states for any x and that guarantees of this is a 86 00:10:05,582 --> 00:10:10,910 deterministic machine. Each machine, each state will only have one possible move on 87 00:10:10,910 --> 00:10:15,504 each input so. We can just, now it goes to our check list and see if we have a 88 00:10:15,504 --> 00:10:20,125 deterministic machine. We have a finite set of states. We have a start state and 89 00:10:20,125 --> 00:10:24,979 we have a set of final states and we have a transition function with only one more 90 00:10:24,979 --> 00:10:29,541 per input and no epsilon moves. And so that is in fact a deterministic machine 91 00:10:29,541 --> 00:10:34,661 and the property that it maintain is that each step of computation. The state of the 92 00:10:34,661 --> 00:10:40,242 DFA records the set of possible states that the NFA could have gotten into the 93 00:10:40,242 --> 00:10:48,013 same input So let's work to an example of constructing a Deterministic machine from 94 00:10:48,013 --> 00:10:52,335 a Nondeterministic machine. Here's the Nondeterministic Finite Automata that we 95 00:10:52,335 --> 00:10:56,821 built in the last video and again this is the one that I used at the beginning of 96 00:10:56,821 --> 00:11:01,084 the video to define epsilon enclosure. So we're gonna do the example slightly 97 00:11:01,084 --> 00:11:06,068 differently than the construction I gave on the previous slide. If we actually have 98 00:11:06,068 --> 00:11:10,660 to write out all the subsets of this many states, it will take us a very, very long 99 00:11:10,660 --> 00:11:15,308 time. And it turns out that not all of the subsets were actually used by the DFA. So 100 00:11:15,308 --> 00:11:20,012 we're just going to enumerate the states that we actually need and we'll do that by 101 00:11:20,012 --> 00:11:24,828 beginning with the start sta te of DFA and then working out which additional states 102 00:11:24,828 --> 00:11:29,308 are required. So how do we do that? Well, we begin with the start state of the NFA 103 00:11:29,308 --> 00:11:34,655 which is just this state a. And then recall at the start of the DFA is the 104 00:11:34,655 --> 00:11:40,694 epsilon closure of that state so that corresponds to this purple set here. 105 00:11:40,694 --> 00:11:47,223 Alright. So the first state of the DFA, the start state is the subset of states a, 106 00:11:47,223 --> 00:11:52,807 b, c, d, h, i. And now we have to work out from this particular state from the start 107 00:11:52,807 --> 00:11:57,316 state what happens on each of the impossible input values. So, the alphabet 108 00:11:57,316 --> 00:12:02,251 of this machine is one and zero so you would have to have two transitions out of 109 00:12:02,251 --> 00:12:07,429 the state, one for an input of one and one for an input of zero. So let's do input 110 00:12:07,429 --> 00:12:13,580 zero first. And, we can see looking at the purple set that there's only one possible 111 00:12:13,580 --> 00:12:19,700 transition and that's from the state D to the state F. So certainly the state s is 112 00:12:19,700 --> 00:12:25,731 included in the set of states if the NFA can reach but then once we get the state f 113 00:12:25,731 --> 00:12:31,690 there's a lot of epsilon moves that we can take and so in fact the second state of 114 00:12:31,690 --> 00:12:37,578 the DFA corresponds to a much larger set. It's all the, it's the epsilon closure of 115 00:12:37,578 --> 00:12:42,963 f and that is, this set of states f, g, h, i, a, b, c, and d, okay. So these are the 116 00:12:42,963 --> 00:12:49,019 set of possible states that the NFA could be in after reading a single zero. Next, 117 00:12:49,019 --> 00:12:54,656 let's consider what happens from the start state on an input of one. Which possible 118 00:12:54,656 --> 00:13:00,292 states can the NFA reach? And, if we look at the transition function, we see there 119 00:13:00,292 --> 00:13:05,850 are two possible moves that the NFA could take. It could be in state c. In which 120 00:13:05,850 --> 00:13:11,651 case it would move to state e or it could have been state i, that's also part of the 121 00:13:11,651 --> 00:13:17,186 purple set in which case it would move to state j. So, there are two possible states 122 00:13:17,186 --> 00:13:22,720 that the NFA can get into as a result of reading a one and then after that, there's 123 00:13:22,720 --> 00:13:28,122 a bunch of epsilon moves that can take place and in fact, it turns out that after 124 00:13:28,122 --> 00:13:33,876 reading a one, the machine could be in any state except for state f. And that's this 125 00:13:33,876 --> 00:13:39,307 set of states and you'll notice that this particular set of states, the read set 126 00:13:39,307 --> 00:13:44,873 includes the final state of the NFA so this is also a final state indicating that 127 00:13:44,873 --> 00:13:50,101 after reading one, the NFA could be in an accepting state. So this would be an 128 00:13:50,101 --> 00:13:56,718 accepting state of the DFA Well, we still have to fill in for both of the two states 129 00:13:56,718 --> 00:14:02,695 that we've added here. The two states on the right of the machine what they do on 130 00:14:02,695 --> 00:14:08,409 input zero, what they do on input one. So let's figure that out. So beginning with 131 00:14:08,409 --> 00:14:13,283 the red state on input zero, what can happen? Well, look the red state includes 132 00:14:13,283 --> 00:14:18,474 state d and it can move to state f but we've already computed what happens on the 133 00:14:18,474 --> 00:14:23,728 epsilon, what the epsilon closure that is just the green state. And so if I'm in the 134 00:14:23,728 --> 00:14:30,176 red state and I read zero, I move to the green state. If I'm in the red state and I 135 00:14:30,176 --> 00:14:36,645 read a one, you'll see that both states, NFA states c and i are in the red set. And 136 00:14:36,645 --> 00:14:42,640 so, it just takes us back to the red set. And similarly for the green state, if I 137 00:14:42,640 --> 00:14:48,097 read a one, I move to the red state. And if I read a zero, I stay in the green 138 00:14:48,097 --> 00:14:53,123 state. And so, this then is our deterministic machine down here. This is 139 00:14:53,123 --> 00:14:58,723 the deterministic machine and again, it simulates the NFA. So every move at the 140 00:14:58,723 --> 00:15:04,611 deterministic machine, it records the set of possible states that the NFA could be 141 00:15:04,611 --> 00:15:10,140 in and it will accept a string infinitely if the NFA could accept the string.