Finite State Machines

let's get started with this course this is perhaps the most abstract course in the whole curriculum but I think one of the most fundamental courses for any computer scientist to know now the really interesting stuff in this course is not going to help you write a program per se and it's not going to help you build a computer per se but it will help you understand a lot more about what people have thought about in the last 50 years about computer science as a science and it's about what kind of things can we really compute mechanically how fast can we do it and how much space does it take us to do it how much memory does it take us to do it and because of that the course is called theory of computation so like like lots of abstract courses and courses that have a lot of really cool thinking and neat stuff in it especially in computer science there are lots and lots of applications that come out of this course things that are pretty much serendipitous all of compiler design and theory about building compilers and writing programs to translate languages comes from theory of computation another direct application either but more a kind of a side effect it turns out that some of the models of computation that we discuss happen to correspond to programs that help us write compilers and there are lots of other applications as well when you talked about computer architecture you modeled a particular processor with a finite state machine the idea of the finite state machine originally comes from theory of computation when you do any string searching and any word processor or any kind of editor that uses a finite state machine when you do any kind of compiling or representation of a language like XML you describe it with a grammar and that grammar is the next level of model of computation so what this course talks about is different models of computation different kinds of things you can use to compute stuff now what does it mean to compute something in this class it's going to be something very very simple because we want to abstract it all away from the specifics of the Machine and all the specifics of problems you see so we abstracted away in this in this style we imagine that all we're doing is dealing with programs or computations that take an input somebody sends it an input and the program sits and stares and thinks and thinks and calculates and computes and then says yes or no do I accept this input or I do not accept this input no actual number crunching or anything like that whatever number crunching involved is all in order to decide yes or no so in order to do that we simply think of things we want to compute as a set of things and normally the things are very simple we pick an alphabet it can be as simple as a binary alphabet and it could even be a unary alphabet just one symbol and we consider strings along that alphabet so what's an example of something you might want to compute say the set of binary strings that means strings over the alphabet 0 1 that end in 0 not a very hard thing to compute somebody gives you a binary string if you're a human being just look at the end of it you see if there's a 0 if there is you say yes there's not you saying no you can all write a computer program to do this certainly you could have probably done at some of you before you came here it's a very easy program you look at the end you see if there's a zero there are other things that are harder what if you took a piece of Java code and turned it into binary file and wanted to know whether that really came from a legitimate piece of java code or whether it's just some junky binary file that represents something else does this binary file represent a legitimate Java program or not so we can write the set of binary strings that represent legal Java programs so can you do that can you write a program that does that and I mean you personally could somebody write a program that does that they better be able to otherwise when you write your Java program and you say run this what checks that it's a legitimate what's giving you all those error messages right it's not some little mouse sitting in the machine saying that's not right error on line 32 or there's a program that looks at this and that does it and it does more than just say yes or no it actually spits out output that's what compiler design is all about so that you can still do but it's a lot harder computation than that and let's go one step further the set of binary strings that represent legal Java programs that never infinite loop that's probably not English but you know what I mean loop is a verb there that never go in an infinite loop no matter what input you would give them is there a program that will look at your java code and tell you that yes or no an answer is there isn't any such program it's impossible there's no way to compute this no matter how hard you try it's not going to work it's going to either give you the wrong answer or it's going to run forever and never give you any answer your program that you try to write to do this doesn't exist so that's what we're talking about in this class what can you compute and what can't you compute and what kind of models do we have to do this computation your own sense of how you do computation now is a programming language you know scheme you know Java that's one thing we're going to abstract all those details away and get down to the root of what a programming language really is and maybe the most popular way to view a programming language with everything stripped away is called a Turing machine invented by Alan Turing and it's a very simple machine we won't talk about it yet today we're going to build up to a Turing machine but Alan Turing in the nineteen kind of in the 1940s when he invented this he died in the 1950s invented an abstraction a mathematical abstraction that he thought was a complete representation of how we might do computation to the extent that anything that you do on a normal computer with a normal programming language could be done on his machine you could write a program for his machine that does the same thing and his machines very very abstract and simple but because of that we can prove really interesting things about it like the fact that this can't be computed so what we're going to do in this class is work our way up from a much lower level one thing when you define something abstractly is here's a nice chugging machine it's got arms it's got legs it's got a brain what if I cut off its left arm can it still do everything it could do before but just take a little longer or is it actually handicapped and it can't do certain things that it used to be able to do for example the set of binary strings to represent legal Java programs I know that I can write a program to accept those therefore I'm sure I could write a program for a Turing machine that would accept those but what if I cut off the Turing machines left arm metaphorically is it possible that I can't do this anymore and I'm cut back actual power or maybe it just takes me longer to do it those are the kind of questions people ask in this class in this course that's the kind of question scientists wonder how much can I chop off of a Turing machine and still be able to do it and then we're going to abstract it out we're going to start with the lowest level which is a finite state machine and we're going to work our way up building pieces on it until we get up to a Turing machine and then start exploring the twilight zone which are problems out here which can't even be computed by a Turing machine all right so that's that's the big picture other questions of that about that so far little bullseye one more the simplest kind of machine we're going to consider is one that doesn't have as much power as programming languages one that's simpler called finite state machines I'm abbreviated FSM finite state machines and you've seen these before and you've seen their applications before that's the smallest simplest level they can compute certain kinds of sets they can decide certain kind of things like whether there's a zero on the end of a string but they can't do things more complicated like figure out whether something is illegal Java program there's a lot of other things they can't do also there's a lot of interesting things they can do outside of this if you add on some power to the machine is a class of sets that can be recognized by a more powerful machine and those sets are called context-free languages a set of strings is often called a language not at all to be confused with a programming language a language is nothing more or less than a set of strings so the set of strings that have zeros at the end of them that's a language and you can recognize it with a finite state machine context-free languages are languages that are more complicated than the ones that are up that can be accepted by finite state machines and they also include the finite state machines also so there are a larger group all the stuff about compilers legal Java programs all those sets of strings those languages they're inside here so legal Java programs are in here in context-free languages then we bump up another level to Turing machines that's full level computation that means anything that can really be computed with a computer with any normal programming language can be computed by these machines so this includes everything that you know how to do and way out here the twilight zone our problems that we call undecidable there's no program anywhere mechanically that can figure out the answer to these questions in general no algorithms to figure out the answers this is a blueprint for the course now I should say as we get into more detail this blueprint will become more refined there are sub sir goals there are sometimes overlapping circles there are all sorts of other relationships between these levels inside the Turing machine level itself there are hierarchies P and NP are both inside the Turing machine level okay if I made another sub circle P would be on the inside NP would be on the outside there's a whole hierarchy of complexity theory that takes place here all the applications to compiler design take place here and all the applications with finite state machines take place here but it's just hierarchy that'll give you a blueprint for the class yes they all represent machines with different amounts of power and well you'll see that there's different ways of actually describing languages one way is by a machine another way is by a grammar and a third way and it works only on some levels is by something called expressions so there's different ways of describing these classes of sets of strings or languages but you can think of it for sure as just more powerful machines going up the line this level in particular is going to be split into two it turns out that the two levels that this splits in two end up not giving any extra power in these levels in other words there's an extra booster arm that you can throw into finite state machines but it turns out not to give it any extra power you know it's like if somebody runs a marathon in four hours and you give them lots of extra carbohydrates before so they'll run the marathon in 350 but it's not going to make them a really better marathon runner so they stay the same they're just a little faster but in this level if you throw in a little bit of extra power you actually end up gaining new languages you couldn't do before and it splits the set into two back in this level when you throw in that extra bit things stay the same again so this level will get partitioned later on whoo all right so it's fine to get down to some more specifics okay let's start down here you've all seen finite state machines before I'm going to pretend you never have and I'm going to teach them like I always teach them you're going to read the book the book has tons of formalism even though it's a very nice intuitive book there's lots of ideas behind the proofs nevertheless to write a real book for this stuff you have to be very careful make sure you don't say anything vague that's exactly the opposite of what's going to happen in class I can say all the vague things I want because I want to give you the idea of what's really going on and if you want to find out the real nitty-gritty detail and if I say something it isn't a 100 percent completely rigorous it's right there for you to check and I just asked me a question too because I know all the rigor behind it but it's just really bad to teach this course by by going toward rigor some of you might have remembered some of the speakers we had during this year one of them particularly talked about this stuff and and did exactly that and it just it seems much more difficult than it really needs to be so I'm going to explain what a finite state machine is by showing you an example and then pointing out in the example what the real traits are so let's let's start with an example let's start with strings that have an even number of zeros binary strings that have an even number of zeros I should mention our sets of strings that we're talking about they don't have to be over the alphabet zero one right I mean Java programs are over an alphabet of of A to Z and 0 up to 9 and commas and semicolons and various other things parentheses close parentheses so this alphabet can be very large but for the purposes of understanding the abstractions and what's really going on in this class we hardly ever need to consider alphabets that are more than two symbols two symbols kind of gives you this exponential help over one symbol and after that it's just convenience so we'll always assume that it's binary strings unless I say otherwise so we want to consider the set of strings that have an even number of zeros instead of binary strings with an even number of zeros and we're going to describe these things called finite state machines by actually doing it for this for this problem so here's what a finite state machine looks like it has States the states represent some kind of memory about the problem that you're dealing with if you want an intuition for what can be done with a finite-state machine it's anything you can do and solve by remembering a finite amount of information if you use that gut instinct rule you'll be able to almost triage any set and say yes or no it can be done with a finite state machine or not if you ask yourself can I write a program for this using a finite amount of memory could I figure out how to do this storing a finite amount of information so in this case I want to give you a sense of how to do the design of finite state machines this is going to be an easy one but there's plenty of hard ones you really want to get a semantic meaning to each state so this state will be things with an even number of zeros and I have another state that will be an odd number of zeros and we're going to start here meaning that before we've seen any symbols of the string that we're considering we now have an even number of zeros namely zero zeros we haven't seen anything yet and now the machine is going to imagine the machine looks like that's it it's over here and then there's a little tape here that has a particular string on it 0 1 0 1 1 1 so this should be accepted it should say yes the machine is going to have a little head little arrow a little head that looks at the symbol and moves strictly left to right across this tape and as it moves it moves from state to state that's all it does that's the simplest kind of computation you could possibly have remember a finite amount of things read your candidate string left to right and move back and forth so let's put in what's called the transition function the thing that tells us where to go as we see symbols if we're in this state we have an even number of zeros and we see a 0 and we're going to switch over to that state and what of what else might we see we might see a 1 instead of a 0 what would we do then stay here and that takes care of this state in fact every finite state machine should have exactly one error coming out of each state for each of the symbols in your alphabet so in binary strings you got two arrows coming and now you move on to the next state and in fact if you structure your design to finite state machines in this way actually writing the states down first without any arrows modeling the problem semantically by giving information in the States and then only later filling in the arrows you will have a much much easier time doing it and if you have trouble deciding what information needs to go in the states that's where you should stop and think and not after first putting in some arrows because that will just get you perhaps on the wrong track alright so who can fill the rest of this in for me smiley Donna done good all right this is 80% of a finite state machine this error indicates that I start here in the state there's one state that is uniquely given as the start state that tells me where I begin these arrows tell me where I go based on different symbols and there's one more piece of information and that is a set of final States a subset of these states where if I actually end up there when I'm finished reading the string tell me that I accept it and I say yes and if I end up in the non final states I say no and the way to indicate final States in my notation and I'm pretty sure the book does the same thing is just to put a double circle around the state so that's this one that's a complete finite state machine this accepts all binary strings that have an even number of zeros and it rejects all binary strings that don't have an even number of zeros and we can run it 0 1 0 1 1 1 I end up here I look at the double circle I say we I accept and that string is a yes all right other questions so far who's got it too easy so far too easy good nothing like too easy ok yeah yes all yes no answers yes there is issues of complexity it's not that the other questions aren't interesting it's just that let's let's solve these questions first because they're hard enough it's hard enough just to deal with computation with yes or no and then later on we can put in the issue of actually outputting something because we do do that later on as the Turing machine level in fact you might remember in the computer architecture course they talked about the versions of finite state machines that actually have output mealy machines and Moore machines is that ring a bell okay so there are versions of this that have output and sometimes and of course like this you know they get thrown into the exercises as hey somebody uses this for some neat application but you've seen that application already and and for the most part we don't need to to discuss it as far as the material in this class goes we're not we're going to stay away from output on finite state machines they just say yes or no all right so we're going to do a few more examples of this and an even number of ones it's another thing a finite state machine can do all right so the last one that I did is the last one that I'm going to do for you so now you guys do it and I help out and I correct you when you're wrong and that way we'll discover this together how do you do all binary strings that have an even number of zeros and an even number of ones what's the plan don't say okay write the circle and make an error tell me how you want to represent the state how many states should we have whether what are the issues whose an idea yeah so you want to do all the possibilities of a number of zeros and ones whether they be even or odd and you are alarmed in discrete math if you have two bits and you want all the different possibilities at 0 0 0 1 1 0 0 1 1 got 4 possibilities you think that's a good idea looks good to me all right so I got four states I can name that tune in three notes maybe not three here's a fire yeah that's a finite say mission through yet here's the initial state what should this one be even even zero is right so how about if I represent these states by by two letters E and O EE for this one even even so I don't have to write even number of zeros even number of one this is e e and this will be e oh and this will be oh a and this will be oh oh all right so let's let's go through and figure it out what happens when I get a zero here I got to tell you which one is which the first one zero is the second one ones so if I get a 0 here I toggle this one and if I get another zero from here I toggle it back fill in those two first if I get a 1 here I toggle this one and if I get another one I toggle it back Doug laughs on the rest what happens here okay okay this way this is that it that we have zeros and ones come out of every state and it's right so where should the final state be this one all right notice there is not always a single final state what if I gave you this problem I want something with an even number of zeros and an even number of ones or an odd number of zeros and an even number of ones then it would be both of these being in the final state now what I did do that once I changed it so now this was the machine is this the smallest machine that would do this what is this equivalent to this set of things with an even number of zeros and an even number of ones or an odd number of zeros and an even number of ones very much like it not quite excited this is an even number of ones so in some sense this is not the smallest finite state machine definitely not that we could do this with two states these two are essentially equivalent and these two are essentially equivalent for our for all intents and purposes that's a very important thing to realize when you realize this for the first time you say oh gee I wonder if given a particular set of strings there's always some minimum finite state machine that I can get you know there's clearly more than one so maybe there's like one canonical minimum one and and all of those look the same and the answer is that there is and that's a very very nice thing to have about a machine because there is no canonical minimum program to solve any of the programs you've done this year everybody comes up with a different one there isn't anything special you can say about the best one of the smallest one but for finite state machines you can and there's a very very rigorous algorithm that does that minimization and it's a dynamic programming algorithm so everything all comes full circle and we'll talk about that algorithm later but it's important to know that there is a minimum finite state machine for every set that that you can accept okay let's go on to another one divisible by 4 how do you know if a how do you do it how do you check if a binary number is divisible by 4 well let me pick the bad way I always like to do the wrong so here's a bad way I'll take the binary number I know how to convert it to base 10 because I don't really understand binary numbers better remember the algorithm so I go ahead and add it all up I convert it into base 10 and then I look at it in base 10 I know how to do division so I do 4 into base 10 and I do division and I know if there's a remainder or not and if there's no remainder then I say yes that's perfectly okay I mean it's a computation and it's deterministic I'm never going to infinite loop in that computation but but it's kind of like it's kind of like you know tying your hands behind you and then trying to tie your shoes it's just a hard way to do it it's a little easier to look at a binary number and decide if it's divisible by 4 then first changing it to a base where division by 4 is not obvious and then doing the division the division by 4 is kind of obvious any division by a power of 2 in binary is obvious if I gave you a base 10 number and I said is it divisible by a hundred what would you do you'd look at the ending and see if there's two zeros that's the same thing here that's 10 squared this is 2 squared if you want to know if a binary number is divisible by 4 you just look at the last two symbols so this is just the same as binary strings that end in 0 0 all those things are divisible by 4 so let's do that let's write a machine that figures out whether a binary string ends in 0 0 beginning in 0 0 would be easier right right I mean let's do that one at least make sure we can do it here's beginning in 0 0 I haven't seen anything I've seen a 0 I've seen another 0 now I don't care what I get and what if I get a one go somewhere else what if I get a one I go somewhere else and I call this the dead State I never except from there and these are all the strings that start with two zeros everyone agree it's not what I want I want strings that end in two zeros but at least let's do something similar to what we want that's easy and maybe it'll give us a hint for what we want to do by the way what's the meaning of these states this state is I haven't seen any symbol yet this is I saw zero this is I saw two zeroes kind of obvious meaning how do you decide if you want to end in two zeros this is harder to zeroes along the top like you started and in the end instead of just looking back so this third circle if you get one you look back start over if you don't have any zeros then okay let's doug has a good idea let's look at it he says let's start with the same two zeros in the sense that these are the last two symbols we've seen this means that my last symbol is a zero I'll write that in here last two symbols are 0 and this is last symbol second last symbol is a zero right that's what these things mean the second-to-last symbols is zero the last two symbols are a zero that's the case we want to accept well now we've got some semantic meaning on these states we just have to fill on the other arrows and that's what you were doing in your head but now I think we can do it now that we have some meaning to these states if we haven't seen any symbols yet in this spot and we got a 1 then what and we stay there then we still haven't seen any zeros you what about here if we get a 1 we haven't seen any zeros yet this is the last symbol the second-to-last symbol is no longer is 0 right the so we go back here what about over here back to the beginning do we finish this so we have zeros and ones on every state so let's test this does it really work or is it mistaken or is there a problem say it again set and zero is divisible by four right so if I have so the empty string I'm supposed to accept right and any string of zeros I'm supposed to accept even a single zero so can I just make that a final state no right we make our starting point we did the final state then it should work because if we get a zero so let's take away the starting state which we maybe were too rash and how we started because after all this is the place we started when we wanted the thing to start with two zeros maybe we can put the starting state here that's an idea let me stop for a second before we check this if you're thinking oh gee how will I know to design harder ones than this then let me give you the answer straight up from the beginning this is a design process and there is no algorithm for making finite state machines for particular set and everyone is a creative process and some are harder than others and some you can stare it all day long and not know how to do and some you'll get right away so there is practice involved and there's tools that you develop and that's why we're doing these examples let's check this now so Seth had a good objection he said we're not accepting single zeros and we're not accepting empty strings well now we kind of are right we certainly select the empty string do we accept a single zero yeah right well that's another thing we never finished this machine right I said it's finished over zeroes and ones that have every air I lied right there's no zero out of here zero should go back to itself if the last two symbols were zero and you get another zero then the last two symbols are still zero so now we've got that nice accepting single zeros we accept the empty string and we accept anything that ends in to zero so there was a there was a process here in a Discovery and it took a little more time let me give you a faster way that we might have done this if you had known something in advance let's say you knew that if you could accept a particular language that you knew a way to accept it's reverse let's say anytime you knew a language and how to do it and how to make a machine for it and I told you do it for the reverse of that Lang what is the reverse of the language means it means every string in the language just gets reversed so what's the reverse of things that are divisible by for things that start with two zeros what if you always knew given a machine for one set how to get the machine for the reverse what if there was a process an easy process then you think about this you'd say gee ending with two zeros that's like the one we did in class and it wasn't quite so easy so but I know a really easy way to do things that start with two zeros I'll just do that and then I'll figure out the way to reverse it right so there is a way to do that and there's a way to do lots and lots of these what are called closure operations there's a way to do reverse there's a way to do many many things like it there's a way to do compliment and these closure ideas are a key thing that people think about when they talk about models of computation not just because it's interesting mathematically but because it gives you a whole repertoire of tools to decide whether or not a set can be accepted by a finite state machine and how to do it knowing the reverse year would have helped us we did it anyway because we're smart but you never know when that's going to fail you okay what if I ask you for all the binary numbers that aren't divisible by 4 do we start from scratch yeah what if I just take this final state good idea Shawn make it a non final state and take these two final step to non final states and make them final States I just toggle all the final and non final states whatever used to not be except that I now accept and whenever used to be except that I now don't accept and that actually is a good enough proof that finite state machines are closed under compliment that means if you can do one kind of set you can do its complement just toggle the final in on final States right so that's the first closure proof we've actually done it's pretty straightforward there's a lot of other ones that we'll get to later all right any more questions about this one one zero one one zero I mentioned that one of the big applications of finite state machines are building string searching tools in editors so while here it is here is a string we want to search for build me the finite state machine that accepts any string that contains this and then you could actually implement that as a program and and that's there's actually not obvious ways to do it there's a lot of good and bad ways to do it there's a whole area in algorithms called string matching and it's based on finite state machines and it's clever ways of implementing finite state machines in order to search for strings and the first one of those was due to Knuth Morris and Pratt and I think we even did a recitation on it back in a few months ago but now let's just write a finite state machine straight who's got an idea where do we begin here Chris you have a series of states representing progress along that line okay we're going to have a series of states that represent how much of this string we've seen and if we actually see the whole string then at the end we'll put a double circle so let's look through that we start here I've seen a one that's good I've seen another one that's good I've seen a zero very fine a one one zero and I accept here and I'll put little semantic notes in my states here I've seen nothing the book uses an epsilon or an e to represent the empty string some books use a lambda to represent the empty string different books use different things and I will try to use Annie but sometimes I may forget and use a lambda it just means no string at all just the answer the null the zero ASCII value this says I've seen a one that says I've seen two ones I seen one one zero I've seen 1 1 0 1 1 1 0 1 1 and here I've seen everything alright so now we just got to fill in the rest and how easy or hard is this well let's try and see say I'm here and I get a 0 then how much of this string have I seen none of it say I'm here and I get a 0 then I've seen a 1 0 that means I've seen none of the string back to here here I've seen 1 1 and if I see a 0 I go here what if I get another one because I've still seen 2 1 right you can all see that this is a little bit you got to use your head when you're doing this there's actually a complete mechanical process to build this machine and that's what the knuth-morris-pratt algorithm is all about it's how to build up an array that represents this machine in linear time without having to do too much thinking we're kind of doing it by thinking man we do everything by thinking maybe not everything now what 0 there 1 1 0 then we get another 0 we haven't seen any of the string then back to here 1 1 0 1 if we get a 0 I think we're back to the start again mostly no I don't think so if we get a 0 here I don't think we've seen any of the string yeah now what about here 1 1 0 1 1 1 then how much of the string have we seen 1 1 0 1 1 1 we've seen two ones okay this is tricky 1 1 0 1 1 1 how much of this pattern can we pull out of here from the right end that's as much as we can if we go back one more symbol we have 1 1 1 and that doesn't match so what you're really asking is how much of this pattern can overlap with the right side and you can you can imagine there's probably some mechanical process to do it in there is and it's clever so this goes back to here on a1 and finally here on a zero or o1 we've already seen the whole string it doesn't matter what happens okay and of course if I wanted all the strings that don't contain this as a substring I just turn that into a non final state and turn all these into final states the reason I mentioning that is because if I started with that example it might have taken us longer to discover this idea the way to do things that don't contain this string is really to do things that do contain the string and just flip all the states it's very hard to focus on the characteristics of strings that don't contain this explicitly and it actually ends up being six different kinds of things we could actually give meanings to each of these and if you tried to do it that way you would have spent a lot of time so doing it this way is a quicker and a faster way all right keep this example in mind because when we add on an extra arm to this machine we're going to give it power we're going to get a power that turns out not to actually help it at all but just help us write easier machines when we give it this power we're going to be able to write this example like that in a flash and we're going to need a proof that this power can always be converted back to something without the power but there's always a way to take these fancier machines and write them without the fancy stuff and this power that we're talking about that we'll get to before the end of the day is called non determinism and you heard it before in the algorithms cost but now you're going to get it by a real definition and not just by an algorithm intuition all right oh yeah well I've got the compliment for sure but the compliments different than the reverse the compliment is all the things that are not in this set and the reverse is take all the strings in the set and reverse that so that they might be different things you mean to reverse it well I guess I get strings that contain 0 1 1 0 1 1 is the reverse of this right well so you're asking yourself a good question if I have a finite state machine how do I get a finite state machine that accepts the reverse language we haven't discussed it yet I said it could be done you know what I'll come back and we'll try to do it yep it's a good question let's let's try right now what would you do the arrows would have to be reversed right the arrows go in the opposite direction and what about the final and initial States we want to go backwards so we kind of want to start where we end and then we want to and where we start so look what happens when you do this kind of strange transformation we reverse all the arrows boom I reversed them poof I turn this into a start state and I erase its final state and I turn this into a final state what do you notice about that machine there something really strange about it hmm you've got an arrow well you have an arrow that goes back to itself that's okay this is reversed now right what you can see all the inputs and they can't loop back to itself and all the inputs true that's true and there's two zeros so what do I do when there's a zero do I stay here or do I go that way right so it was a really good idea to reverse the arrows and to switch the final and and and and and the initial States but when I do it I get a machine that doesn't even make any sense and it seems to be wrong so so right I mean well I guess how wrong can you be when you don't make any sense here's the thing this is a good idea the idea is very good it's just that this really begs us to ask the question well what does it mean to have a choice on the same symbol if we can make sense out of what that means maybe this method actually really works it turns out this method does work we just have to explain what it means to have two symbols the same thing we if we say it's meaningless or if we say oh we might get stuck here then then it's going to be wrong but if we give it correct meaning there is a way to interpret this reverse and then convert it back to a deterministic machine and we would actually get the reverse so it's the right idea it's the right idea and it's the right idea and it's going to introduce non determinism in about five or ten minutes non determinism is exactly this you can have more than one error coming out of a state with the same symbol on it so the question is what does that mean how do you decide what gets accepted and what doesn't get accepted in a machine that doesn't tell you what it's doing in any state I'm going to do this or this yeah all right we'll talk about that in a few minutes I'm going to do one more of these well two more here's a quick one every one is followed by at least two zeros binary strings again every one is followed by at least two zeros I want to do this one because instead of giving the state semantics meaning right away this one is more of a left to right let's imagine that we're the machine how would we do it this is much more of a real-time left-to-right processing thing not a recursive idea not a semantic idea let's go ahead and start here's the start state if I see a zero I don't need to do anything special but if I see a one then I'm in a state that remembers that I'm now in the second stage of my computation sometimes states don't have semantic memory so to speak but they remember where you're up to in the computation I've just seen a 1 now I need to get at least two zeros otherwise I don't accept so in order to continue there have to be two zeros that's my continuing step if any point along the way I didn't get a 0 I died 1 1 the dead State yes directly file it yes yes yes right I know you know what I meant yes Thank You Donna if there's two zeros afterwards then what then we're okay and we got to look for where are we and where should we continue is this machine going to go on forever you know sometimes finite state machines going through its seatback so when it goes back okay so can i Tony's right on a zero we'd stay here and on a one we could go actually to here under one and if that's the case then these two states are for all intents and purposes identical I'm pointing it out because that's the idea of minimizing machines what you try to do is notice groups of states that actually do the same thing for whom it doesn't matter where you start they always tell you yes or no together so actually I made a new state here but I just realize that it's the same as this state so now I go back and I just wing that arrow back to here and that's okay right what you said is fine to Tony it would work just as well just the state shorter this way all right okay this example one more example and then and then we're done this is a little bit trickier but not too bad find the restrings that are not divisible by three so now you don't have the nice just you know power of two thing where you're going to look at the end of the symbols now you really have to do division in some sense on this binary string now when you do division at least the way you learned it when you were in third grade you have to store a lot of information I mean you have to remember it seems you know the result as you go along and that's proportional you know to the size of the string you have and that doesn't seem like it's constant if I give you a longer string it's going to take you longer a bigger amount of space to do the division and that's true division actual real division as a computation does take space that grows and is not finite that's proportional to the log of the size of the string so we can't do real division so how are we going to do this well we don't really have to do the division here we have to just figure out whether it's divisible or not and in order to do that we just have to figure out what the remainder is and you were never taught just to figure out the remainder when you're in third grade but if you were they could have taught it to you and you all you have to do is remember one or two or three numbers as you go along so let's consider what that means before we write the Machine this is much harder this you can sit up for a few hours if you don't get the idea right away let's do this here's the number we want to know if it's the visible by three well let's not convert it to base ten and do the division in our head because that's that just begs the question instead let's pretend we're the machine and we get to look at this left to right so now we're staring at the one let's say that was all we got is it divisible by three or not what is it divisible by what's the remainder when you divide it by three is what I mean one right so that's what we're going to remember we're going to remember if I stopped right now what would the remainder be if I stopped right now the remainder would be one now I'm going to continue I put a zero on the end of my string let's not calculate that this is a two and therefore two is the visible by three let's calculate how the remainder changed when I put a zero on the end of a string whose remainder divisible by 3 I already knew Stuart recursively this is a recursive idea if I knew the remainder was one and I stick a zero on the end of the string what happened to the string in size it doubled in size if I double a string in size and I double its remainder with respect to three if it was remainder one now it's got a remainder two so I double this now it's two how much information am i keeping track of one piece of information what the remainder is how many possibilities are there for that either 0 1 or 2 3 States is enough to do this let's continue when I move on to this third spot double it and add one so if my previous remainder was a two I double that I get a remainder of 4 which is really remainder of 1 then I add 1 which is really remainder of 2 all right so it stays remainder of 2 then I move on to here so another one double it and add one stays two things before and now same thing double add one stays two so when I'm all done I know this has a remainder of two when I divide it by three now I'll check out this the the other way what is this number 1 3 7 15 no geez what is it 1 2 4 16 23 23 so 23 divided by 3 please remainder of 2 good ok let's write a machine to do this you all think you can do it let's try we're going to have three states this one is going to be a remainder of 0 this will be a remainder of 1 this will be a remainder of 2 and I start in the remainder 0 state because when I haven't seen any symbols at all the empty string has a remainder of 0 now let's calculate what happens to the remainder as I add strings on to the right end if I add a 0 I double the string or the remainder so doubling twice nuts and still nothing if I add a 1 I double plus 1 fix try that state let's go here if I have a 0 I double it that moves it to here and if I have a 1 I double it and add 1 which moves me 2 plus 1 is 3 back to here from - if I get a 0 I double it and if I got a one you all know I stay where I am there's beautiful symmetry in this example and here is the final state not divisible by three is here and here this or that this brings up another difficulty with reversing a machine where with my start state B if I if I reverse this machine it could be either here or here right so we have to be really careful with this reverse idea there's there's a couple issues that will that will come up okay questions about this we're done with the examples Brian yeah it has to be either this one or this one but not any other place right the way to really make this reverse is to do something like this have a start stay here get rid of these final states here and say you can go to here or to here without seeing anything see these strange transitions these are called transitions or emove x' or lamda moves and they also make a machine non deterministic because you don't know what it's going to do so there's lots of ways to make a machine non-deterministic double zeros or ones coming out of the state or adding what are called emus and we're going to find out in a little while before the day is over that that adding these things actually doesn't give you any more power I could take any machine like this and convert it back to a deterministic machine and not have all these funny duplicates and that's a nice thing to know because it lets you use these things that will with without thinking you've gone out of your universe okay let's take a two minute brain break for a second and think about something else without the without these examples we did a whole bunch of examples of things that are accepted by finite state machines so I told you some things that aren't accepted by finite state machines but let's try to come up with some simple things that aren't accepted by finite state machines can you think of anything that you'd have a hard time doing and the reason I'm asking you this is because you're not going to be able to appreciate moving up to this level in this level if you think pretty much you could do everything with just this Y have unbounded memory if you just need finite memory then why make up a Turing machine if this represents a computer this doesn't this is limited this is a computer with half its brain cut out right so what kind of strings can't we accept with a finite state machine that are that are easier to describe than just Java program and even Java programs nobody could convince me there's no way to do it I mean I believe you but but it's not like you tried every finite state machine in the world are we still talking uniquely yes no answer yes just uniquely yes no answers so there's a famous one think about what you can't do in finite state machines what you can't really do in finite state machines is count the simplest thing that you can't do you can't count to an arbitrary number here you can go up to 3 do looking for sub strings you can go up to the length of the substring you're looking for finite conditions after a 0 there's two ones you count the finite number of things think of any set of strings you can think of that requires you requires in quotes here because we haven't proved that it reads required but that intuitively seems to need counting anybody come up with one if you read it in the book you can just tell me that's ok too okay so what do you mean the largest numbers yet yeah I need to have like a condition something a Fibonacci numbers okay so the binary numbers that are Fibonacci numbers I'm pretty sure that's not a finite state machine be hard to because it looks like we need some kind of arithmetic calculation that's a good example other example number of zeros and ones that's another very good example for certain there's no finite state machine that will just count the zeros and ones until you if they're equal and even even simpler than that even just this even if all the zeros come first and the ones come at the end you know so that means e + 0 1 + 0 0 1 1 this set dot dot this set there's no finite state machine for well how do I convince you of this except send you home ask you to try and when you stray all night and all 30 of you don't come up with it I'll say well that's 30 more people who haven't come up with it I'll keep doing this until I die and then sooner or later I'll teach 4000 people when I hit 5000 we proved it right we need a better proof and there's a really wonderful proof that there are sets that are not acceptable by finite state machines but it comes up with a very abstract kind of cool set and we'll try to get to that I don't know if we'll get to it today probably in a lecture or two it's a really neat thing because it's used over and over again at the higher levels and that proof technique is called diagonalization we'll go through it in very great detail it's a really neat idea but for finite state machines there's an even easier method of proof that even strings as simple as this can't be done and this proof is going to be very constructive this proof is going to be I'm going to have a discussion with you guys in class I say I challenge you to do this you say I'll do it I ask you a question about what you supposedly did you give me an answer I ask you another question you give me an answer and I nail you down and convince you that you lied somewhere along the way if there really was a way to do this so the proofs in general in this course are very constructive they don't at all you know involve too much it looks like they do if you look at the book but they don't involve a lot of deep difficult mathematics they involve a lot of logic and a lot of straightforward argument and we'll get to those proofs later on Orion machine or did he call us any first name do you know I can't imagine that he called the deterring machine I didn't read the paper and I'm pretty sure he didn't but but I don't know for sure I'm pretty sure he didn't he was a modest guy I remember well first I've ever heard something somebody said last month about somebody naming something after themselves and I forgot what it was it's slipping my memory slip in my mind I next step what I want to do now is talk about the issues that have been brought up intuitively twice already one is when you have a machine that has more than one choice a non-deterministic machine what does that mean and once we determine what it means does it give us power in describing these sets more easily and then how can we convince ourselves that it actually doesn't give us any more power as far as what sets we can compute but just in the sense of how easy it is for us to realize that we can compute them so it doesn't really give us any more power doesn't let us compute anything we couldn't compute before but we end up realizing that we can compute things faster than we used to realize it because we have a more powerful tool it's the equivalent with your machine language as your first programming language and you understand programming through that and you completely can program anything and then somebody teaches you scheme and you go whoo well now it's a lot easier to do recursion and everybody goes well yes it is and things are much easier but there wasn't anything you couldn't do with machine language that you can do with scheme it's just a lot easier to use scheme they're equivalent in power they're just not equivalent as far as ease of use that's what's going to happen here if we tack on non-determinism to a finite state machine they're equivalent power but one is much easier to use so here's non determinism used to save us a lot of time let's do that same example strings that contain 1 1 0 1 1 0 and let's make a non-deterministic machine before we even say when deterministic machine really is let's make one up and by doing this it'll motivate what it is and then I'll explain it so here's a fast machine to accept one one zero one one zero somewhere in this string if we're going to accept it there's an occurrence of one one zero one one zero I don't know where that is so I will read a whole bunch of symbols zeros and ones until I get up to the beginning of that string and when I do I will read that string one one zero one one zero and then I will accept well that's it so you're thinking well that's cheating right well it's cheating so we have to decide what this means give it a rigorous definition as to what this strange machine really accepts I'll convince you after we give a rigorous definition that this machine really does accept exactly strings containing 1 1 0 1 1 0 and then convince you that we can turn these machines into regular deterministic machines and when we're all done it would look like that other complicated one I had on the board that has just a single 0 1 coming out of every circle so what's that process we're converting it and more importantly what does this mean how do we interpret whether we accept or reject a string coming into this machine all right well here's the definition and it parallels what I want this machine to do the definition is if you can look at any string that's given to you as a candidate and figure out some choice through this machine that ends up in a final state then you accept that string there can be lots of choices that don't end up in a final state I don't care but if you can find one one set of choices that end up in a final state then we accept the string so here's an example let's say the string looks like this let's say the string looks like this here's one choice 1 1 1 1 0 1 1 0 there's no 0 out of here I'm dead I don't accept that was a bad choice you can have lots of bad choices in a non-deterministic machine it doesn't mean you reject it ending up in a rejection state on one choice of moves since you have two choices coming out of here when you get a 1 doesn't mean you reject it the only way you reject a string is if none of the choices get you to a final state if a choice gets you to a final state you accept it if none of them gets you to a final state then you reject the string so the definition of accepting a string and these strange machines is this is if there exists some set of choices through this machine that gets you to a final state say yes if there is no set of choices no matter which you choose that ever get you to a final state then say no so should we or should we not accept this string we should because it has a 1 1 0 1 1 0 in it what set of choices will get me to the final state 1 1 and now I don't stay here anymore it's time to move on because I just found the string 1 1 0 1 1 0 and from here I'll chew up anything that comes about so how can I convince you that this machine really works in general not just on this string anytime there's a 1 1 0 1 1 0 in my string I will eat up all the symbols before it ending up here and then I'll choose to move over to the 1 1 0 1 1 0 and I'll end up in the final state and then this will eat up the rest so I can definitely accept all the strings I'm supposed to accept by making that choice how do you know that there aren't other strings that might get accepted by this by accident how do you know that there aren't other strings that don't contain 1 1 0 1 1 0 that might end up here how can you convince me that nothing ends up here except strings that have a 1 1 0 1 1 0 on that because once I start off on this the only way to make it all the way to here is by seeing a 1 1 0 1 1 0 there's no way no matter what choice you make at this point that you could sneak over to this final state without going through a 1 1 0 1 1 0 so this machine as defined by what non-deterministic machines mean accepts the same set of binary strings that contain the substring 1 1 0 1 1 0 and it's also a lot easier to write and in fact it gives you a template for any string searching right just put a 0 1 here a 0 1 here and stick the string you're searching for in between and the non-deterministic choice is over here other questions about this not a terrorism is going to take a little time to get used to there are a lot of things that work with determinism that don't quite become analogous and non determinism so you have to be careful here's one what if I toggle doll the states here I change the final state to a non final state and a non final States the final states in deterministic machines what happened when we did that we got the complement of the set we got all the things that didn't contain 1 1 0 1 1 0 what if I do it here what does this machine accept if I toggle the final and non final States according to the definition of non-deterministic machines it will accept everything as long as this is a final state I have a choice to stay here on everything I can get everything that's not the complement of this so what you should realize is that complementing non-deterministic machines doesn't work by toggling the states the only way to get the complement of the non-deterministic machine is to convert it first to a deterministic machine and then complement it and the reason is that the definition here is not symmetric you accept something if there exists the way to a final state but you don't reject it if there exist the way to a non final state you reject it if all the ways don't exist to a final state so it's that asymmetry in a non deterministic definition that makes this complement thing not work there's a lot of subtleties there and they correspond to non determinism at these other layers so if you get used to non determinism at this layer and we'll be spending some time on it you'll have a much easier time with it as we move higher up the ladder okay questions no because you mean because we don't know what it's going to do well yes and no we don't a deterministic machine we actually think of it in real time we think of it as chugging along state next state next state next state symbols are done I'm done there is none of that with a non-deterministic machine it exists kind of in this abstract world and it doesn't really do any computation on this string per se it does lots of computations you'll see a picture in the book that looks like this and it's a nice picture here's the deterministic machine on this string it starts here and it moves from state to state to state how many symbols here 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 that's a deterministic machine you look here and if it's a final state you say yes if it's not you say no here is the equivalent computation for this machine on the first symbol it has two choices it can either stay here or go there on the next symbol it has two choices on the third symbol two choices a computation for a non-deterministic machine looks like a tree a tree represents kind of all the parallel computations that can be going on at the same time when do you accept the string if there's a path from the start somewhere down that ends in a final state if any of them end in a final state when do you not accept the string when all the paths from the root on the bottom have no final States is that it can't read them all at the same time it won't work exactly the idea the power is that it tries all its possibilities simultaneously and picks the one that works which should remind you of what we did in algorithms that's right that's the connection between what we did there and what we did here non determinism lets you do ORS in parallel this or this or this all get done at the same time that make sense is that helped a little okay something else I was going to say about this once we're here uh this particular branch oh right because when you get to this other spot there's no choice right right so it's two choices on the first one and then this choice doubles with this one a single that's right that's right right I mean if you stayed here you have two choices for the next one but if you move there there's only one choice you also notice that a non-deterministic machines you can leave arrows out if you leave arrows out there just aren't pads there it's kind of like our dead state for the deterministic machine but it's perfectly fine to leave ours out of a non-deterministic machine a deterministic machine needs an error on every state for every symbol so Chris let's do this let's grab the power of a non-deterministic machine and make one that accepts all strings that end in two zeros how do we do it similar to what we did before you have a one in a zero here that just chew up as many symbols as you want and this is similar to trying them all at the same time sometimes people refer to non determinism as guessing since you can try them all at the same time we can also think of it as not trying them all but just guessing the right one if there is a way to do it we like to say we're guessing the right way we're taking the right choice so you hear people use the word guess a lot with finites with non determinism that really bug me when I first learned it go but eating guessing how do you know if you get it right and then later on you guess and you have to check if you get it right and sometimes you check and sometimes you don't so I'm going to try to stay away too much from that term because it bugged me and maybe it'll bug you but but it is a perfectly fine term it just took me time to get used to it you chew up all these zeros and ones and at some point yeah guess that you're done see is you're up to the second-to-last symbol here's a zero here's the last symbol zero and then you except this time there's no no loop on this last state we don't want to chew up any extra symbols we want to really end in zero zero anything out of here is dead and this is it any string that this accepts has to have a zero zero on the end of it otherwise you can't get to a final state and any string that has a zero zero on the end of it has a choice that will make it go here just eat up all the symbols until you get to the zero zero and then move along this path so we accept all the strings with a zero zero on the end and all strings that don't have a zero zero on the end there is no way to accept them therefore this machine works you have to do both those things to describe why your machine works that you accept all the things you're supposed to and that you don't accept anything you're not supposed to because it's easy to accept things you're not supposed to with a non-deterministic machine by accident but we're okay here so now what we're going to do is convert this back to a regular deterministic machine in a mechanical process that will be very logical yeah yeah yeah that would be a oh I see no no because here I mean Neil's asking about this you want to make sure we don't accept something like this right so so it's true you can do 0 1 1 and then make the choice guess now at the end of the string I go 0 0 but there's no arrows coming out of this final state and there's still a symbol left so if we get a 1 out of here I die I crash in other words if you're doing a computation um well I guess it's a new rule in some sense if you're if there's no arrow telling you where to go then then you don't go anywhere then you then you don't except I could just do this also I could put it in like this that would be explicitly putting in the the dead State it would be equivalent but but leaving out arrows means that they go to dead States that's the assumption and non-deterministic machine and you can define it that way optimal string or Ouija just peace you would just be saying that's a good point Sharon made a good point what if you were there and you got another zero right and then it looks like like you rejected it right so how would you accept something like this well the point is that actually we made a bad guess if we pick this zero to be the second to last one we go zero zero and then we find ourselves with one extra string it's true we won't accept it but there's still a way to accept it we just have to make our guess over here so that's an important point it's not symmetrical just because there's a lot of ways to not accept strings you should accept doesn't mean that there isn't a way to accept that did that make sense so the point you brought up is really good and it's subtle yeah that would certainly be fine right right but you know what that's like screaming determinism you have to think too hard and non-determinism your gut instinct should be to leave a blank because you want to end there and you're done but you're a hundred percent right and and it's it shows good understanding of the deterministic way to look at it you could certainly loop back there that would be perfect yeah question exactly exactly that's that's it that's a very good way to put it right Heather's got a good way to describe it if you're actually still reading a symbol and the Machine doesn't tell you what to do that's like that's like you got interrupted that's like you know unknown instruction die and you don't accept so the machine can crash let's turn this machine into a deterministic machine in a way that you'll be able to do for all the others any other non-deterministic machine you have the way to do this is to first label the states we need to have some way to refer to them so call whatever you want a B and C and what we're going to do here has applications all the way throughout this whole hierarchy of finite state machine so I want to make sure everybody gets it we are going to pretend that we are another finite state machine that's deterministic and we are trying to make the decision as to whether this finite state machine accepts or doesn't accept and here's what we're going to do we're going to keep track of where this finite state machine might be we're going to keep track of all the possible computations this might make in another finite state machine that's deterministic it sounds a little vague let's be more specific I start in state a in my new deterministic machine if I see a zero where could I be in this machine I could be an a or in B I'm going to remember that in a new state by just writing the states in there this represents that I could be in state a or b I'm going to make another finite state machine that keeps track specifically of what states I could possibly be in after I've read through any string at all if I get a 1 here where could I be just an a that's easy now I go on to a B I'm an A or B I get a 0 where might I be a or b I get a 0 I could be an A I could be in B or I could be in C yep because of because in it because I might have been an a here and from a and a 0 I could be in being yeah so I could definitely what about a 1 on an A or B well there's no place to go on a 1 from B I crash we'll call it a Heather crash and then from here you're now immortalized and from here one goes back to a so yes they are dead yeah I'm going to leave the dead out from it maybe I should put it in should I put in dead no no it's still deterministic as to possibly they can go on a1 for mayor B I didn't know this state has only one arrow were the ones coming out of it right to put in the ear saying yeah oh we can't just put another one into a dead state right we'll talk about the dead state later let's deal just with the states we have here because all we're trying to do is keep track of where it might be in this machine we don't have to keep track of where it might not be in this machine it's a little tricky where are we done we did zero we did a we did a B now we're going to do ABC if you're an ABC and you get a zero where can you be a B or C and if you're a B and C and you get a 1 back an A well that's convenient now I have no newer new states to deal with if I was in CN I got a zero I'd be dead but if I was in B and I got a zero I'd be in C so so this is a set of places that I might end up assuming that I'm not crashing this is a deterministic machine that is keeping track of where this machine might be after reading any number of symbols assuming it doesn't crash let's run it throw in an example for a day no not really it's really just keeping track of where this machine could be assuming this machine see this machine doesn't really want to crash so let's take it this alive if we run through this machine which is deterministic on a particular string let's actually do it let's run it through on zero one one zero so here is zero one one zero that means I know I can tell you without even looking at this machine that if you ran this on this non-deterministic machine the only places you could end up would be an A or B how I could do zero one one zero that leaves me an A I could do zero one one zero that leaves me in B I can run a machine through on this deterministic machine that you just created and tell you when I'm done where it could possibly be in this machine I don't ever want it to be in a dead State so I didn't keep track of when it might be in a dead State so there's no implicit or dead state because non-deterministic machines only accept things that end up in a final state so I don't really care when things go to dead State so I'm not keeping track of it okay so we're not going to keep track of explicitly if it's in a dead state we could plug into our there's no string that we could plug into our new terminus defense that would they can only go through it that's right right and if there were then there would have been a dead state in here that would have carried over so you can get dead states in here but they have to kind of come from here to begin to understand that a little tricky well let's look at this so now that we have this thing how do you know which strings are going to be accepted how do we take this deterministic machine and make it accept the strings that this thing accept this this thing accepts strings that end up in state C right so if I run through it and I end up here 0 1 1 0 ends up in a B I know I should not accept it he only plays 0 1 1 0 could ever end up is an either A or B that means that it doesn't get accepted by this machine there is no way no matter what choice you make you'll ever end up in state C so you don't accept it what about things that would end up in this state you don't accept them what about things that end up in this state ABC you would accept them because there is a chance for it to end up and C and you're saying what if it doesn't well in non-deterministic machines there only has to be a chance if there's any way for it to end up and C then we say I accept and that's what I kept track of where might it have a chance to end up that's what I care about so any one of these states that contains any final state from your non-deterministic machine becomes a final state in your deterministic machine we're going to double circle this one that means and this is a deterministic machine that does the ending in two zeros is it the same as what we did earlier in in class a little different I think we did it with an extra state right is it exactly the same or not the same I think it's exactly this ain't there so there is a subtle difference between the two but for the most part they're identical this process can always be done say we're going to quit in two minutes now last question of the day when we did this process the number of states stayed the same didn't grow at all there was no trade-off just did a little work we turned non determinism to determinism but there is a trade-off that could happen here it could be worse how much worse can it be how much bigger can this machine be than this machine what kind of payoff is there the payoff is going to be in the number of states here we didn't get any more states once we got these but what is represented in these states how many possible states could have shown up in the worst case combinations or you're thinking the right English word but you're not saying the right math word if the states subsets if the states are a B and C then a state in this machine is any subset of ABC right so we only have three subsets that show up a single a and a and a B and an a B and a C we might have gotten more by going through these arrows forward on zeros and ones what's the amount of subsets we could have gotten with three things to start with how many subsets are there in an N element subset that's why we did a whole month at his feet math way back there who remembers through to the end right so there's there's eight possible subsets none of them all of them every zero one toggle possibility there's eight this machine could have been eight states in the worst case in general the payoff from going from non determinism to determinism or the trade-off or what you have to pay in order to get that is an exponential growth in states now we don't really care because it's still finite but when we talk about things in this layer in the Turing machine layer that exponential trade-off in states turns into an exponential growth in time and it's the same idea and that's why when we trade in non deterministic algorithms for deterministic algorithms we end up getting exponential time deterministic algorithms when we had polynomial time non deterministic algorithms to start with so you see it now in its most fundamental way in this trade-off in the number of states okay so to review we did deterministic machines we explained the semantics of designing them we talked about closure ideas just very briefly we talked about things that might not be accepted by finite state machines we talked about non determinism and its extra power and how it's really not extra power but just extra convenience yeah we'll continue with its stuff next time understanding finite state machines completely they're completely understood it's such a nice level in a layer when we go up higher things get a little more vague

Channel: Chao Xu

Views: 43,897

Rating: 4.949791 out of 5

Keywords: googlevideo

Id: Pt6GBVIifZA

Length: 84min 2sec (5042 seconds)

Published: Thu Nov 22 2012