so um welcome everybody uh to the full 2020 online uh introduction to the theory of computing um 18404 6840. my name is mike sipser i'm going to be your instructor for the semester in this class um so let me just tell you what the course is about um basically it's going to be into two halves what we're going to be talking about what are the capabilities and limitations of computers of computer algorithms really computation um and the two parts of the course are more or less divided in half we're having the first half of the course is going to talk about a subject called computability theory which it really asks what what you can compute with an algorithm in principle um that's a was an active area of research in the earlier part of the 20th century it's pretty much closed off as a research subject these days mainly because they answered all of their big questions um and so uh a mathematical field really only uh stays vital when it has problems to solve and they really solved all of their uh interesting problems for the most part not a hundred percent but for the most part uh it sort of finished off in the 1950s um just to say a little bit more about what we're going to talk about there you know when you're interested to know what kinds of problems you can solve with an algorithm you know there are problems that you might want to solve that you just can't solve for example if you want to you're given a specification for a um you know a computer problem you want to solve whatever whatever that specification might be say you know your algorithm actually is a sorting algorithm for example and you want to write down that specification and have an automatic verifier that's going to check whether a program meets a specification well that's just in principle impossible you cannot meet you cannot make a um a verifier which is going to uh answer in all cases whether or not a program meets a certain specification um so things like that we will prove uh this uh this semester you know questions about mathematical truth what if you're given a mathematical statement is it true or is it false uh it'd be great if you can write a computer program that would answer that problem well it would not be great if you're a mathematician because that would put us all out of business but if you and you know you could imagine that might be a nice thing to have but you can't i mean there is no algorithm which can answer that question um uh well along the way we're going to introduce models of computation like fine automata which we'll see today touring machines and some model other models that we'll see along the way the second half of the course which is going to be after the midterm we're going to shift gears and talk about complexity theory which is instead of looking at what's computable in principle you're going to look at what's computable in practice so things that you can solve in a reasonable amount of time and um for example i'm sure many of you are aware of the factoring problem which has connections to uh the um uh the the rsa crypto system you know cryptography um and asks whether you can factor big numbers quickly um that's a problem we don't know the answer to um we just don't know how to factor big numbers quickly but it's possible that there are algorithms out there that we haven't discovered yet that can do so it's connected with this very famous problem in the intersection of computer science and mathematics called the p versus np problem which many of you may have heard of we'll talk about that we'll spend a lot of time on that uh this uh this term and along the way we'll talk about different measures of uh complexity of computation time and space time and memory you know a theorist called memory i like to call space that's going to be a big part of the course in the complexity theory part introduce other models of computation such as probabilistic and interactive computation uh talk about the expectations of the course first of all prerequisites um you know there are a bunch of prerequisites listed you know 6042 18062 or maybe some other subject as well the real thing is is that this is a math class this is a class where i'm exp you know and it's not a beginning math class this is you know a moderate to advanced math class and i'm expecting people to have had some prior experience you know of a substantial nature with um mathematical theorems and proofs um you know we'll start off slow but we're going to ramp up pretty fast so if you haven't really you know got the idea or gotten comfortable with doing proofs coming up with proofs to mathematical statements you know that's going to be a concern um you can you know i would just be monitoring yourself and seeing how you're doing because the homeworks and the exams are going to count on your being able to produce proofs um and so uh you're gonna stroke be struggling if if that's gonna be a real uh something that you haven't had experience with um so and let me talk a little bit about the role of theory um in computer science is this a theory class um as you know um [Music] so um you know before we jump into the material i just thought it would be worth for you to give you at least my perspective on the role of theoretical computer science within the the the field uh so you know i've been in in in in computer science for a long time you know i go back i'm sure i'm getting to be a dinosaur here but i go back to the days when you had punch cards that's what we did when i was an undergraduate and um obviously things are very different now um and you can argue that in some you know that you know computer science as a discipline has matured and sort of the the basic stuff has all been solved um well i would say there's a certain truth to that but there's a certain way in which i would say that's not true um i think we're still at the very beginning and at least in certain respects of computer science as a discipline uh for one thing there are a lot of things that we do um uh a lot of things relating to computation that you know we just don't know the answer to very fundamental things you know you know let's take in this example how does the brain work obviously the brain computes in a certain fashion um but um you know and we've made good progress you can argue with machine learning and all of those things which that are really doing very you know have very uh very powerful and doing very cool things but i would also say that you know at some deeper level we really have you know the the the um the methods that we have so far uh don't allow us to understand um uh creativity um you know we're not close to being able to create a computer program that can do mathematics or that can do many of the creative kinds of things that human beings can do um you know their i think machine learning powerful as it is is really successful only for a very narrow set of tasks um and so i think you know there's a lot i think there's probably something deeper and more fundamental going on that we're missing um that would be my hunch um now whether something like um theoretical computer science is gonna give you an answer there or this kind of theory or some kind of theory i think some kind of theory has a as at least a decent shot at playing a role in helping us to understand computation in a deeper way and the fact that we can't understand something as basic as can you factor a big number quickly or not um you know you can't really say you understand computation until you can answer questions like that so i would argue that we have a really very primitive understanding of computation at this stage and that there is a um a lot that has yet to be discovered um not just on the technological side but just on the very fundamental theoretical side that has a real shot at playing a role in affecting the practice of how we use computers and so i i think for that reason again i'm not sure what what kind of theory is going to be the most useful but the the theory we're going to cover in this course is a particularly elegant theory and it has already paid off in many applications and in terms of our understanding of computation and i think you know there is um at least as a starting point it's a good it's a good subject to learn um uh certainly i enjoy it and i've spent a good you know good chunk of my my career uh doing that um so um uh let's move on then um and begin with the um uh um the subject material um so we're going to talk about um uh models of computation as i mentioned um you know we we want to try to understand computers and we want to understand what computers can do but computers in the real world are pretty complicated objects and they're really not nice to talk about mathematically so we're going to talk about abstract models of computers that are much simpler but really capture just like models in general capture the important aspects of the thing we're trying to understand um and so uh we're going to look at several different kinds of models that vary in their capabilities and and the way they approximate the real computers that we deal with every day and to start for starters we're going to look at a very simple model called the finite automaton and um that's going to represent uh you can think of it as representing a computer that has a very small amount of memory um and a very limited and small amount of memory and we're going to look at the capabilities of those kinds of machines and what's nice about them is that you can understand them very well um and so um uh more powerful models that we're going to look at later are going to be harder to understand in in a deeper way um but for these we can we can uh develop a very um comprehensive theory and so that's what we're gonna do for the next lecture and a half um so this is gonna i'm starting off with an example i'm presenting a fine art automaton as a um as a diagram we call it a state diagram that is a bunch of has these circles and lines and um uh labels on the on the lines and and also on the on these circles so let what's going on here so this is a finite automaton i'm giving it the name m1 and it has um uh these circles are called states so in this case there are three states q1 q2 and q3 those are the labels there there are arrows connecting once states with each other um so these are we'll call transitions um and they're going to tell you how to compute with this device and there's going to be a specially designated starting state which is has a an arrow coming in from nowhere um and there are certs other specially designated states called accepting states and that's going to have to do with how the machine computes but those are the ones that have these double circles um and so the talking about the way it computes the idea is pretty simple um the input is going to be some finite string of zeros and ones in this case we might have other types of symbols that are allowed for other um automata but the example that i have here it's going to be zeros and ones um and the way you compute with the thing is you uh first put your finger which i can't do um on zoom so i'm going to use the pointer you put your pointer on the starting state the one that has the arrow coming in from nowhere you put your first you put your your pointer there and then uh you start reading symbols from the input uh one after the next so let's take an example here zero one one zero one so you start reading those symbols and you follow those transitions so you go zero this is and you go back to the same state then you go for the next symbol is a one so you go over to this state from q1 to q2 um now you have another one that comes in so now you're starting at q2 you have another one so you follow its associated transition so if you notice every state has an outgoing transition for one and another outgoing transition for zero so there's always somewhere to go every time you read symbols from the input so now you're at q2 you read that next um the third symbol which is a one that's going to take you over to q3 and now you have a zero which loops you back to the where you were and another one which looks you back to where you were and uh because you ended up at an accept um that is an ex you you say we accept that straight um so so that's going to be the output of this um a finite attempt on for each string it's either going to accept it or reject it so it's just a binary decision that it's going to be making sort of like a one or a zero output but we're calling it accept or reject so this one here because it ended up at the accepting state is accepted but if you look at the second example 0 0 1 0 1 so you're going to have 0 0 1 0 one now we ended up at q2 that's not an accepting state so therefore we say we reject this input um okay very simple um and now for example one of the questions you might want to ask given one of these things is well which are exactly those strings that the machine accepts um and uh a little bit of thought will help you understand that and the only strings which are going to take you over to q3 are those strings that have a 1-1 appearing somewhere along the way two consecutive ones and you will end up at the accepting state um um you have to i mean i encourage you to think about that uh for a minute if not immediately obvious but those are the strings that are going to be uh accepted by these this machine and we call that collection of strings the language of the machine um that so that set a of those strings that have a 1 1 for this particular machine is the language of m1 we also say that m1 recognizes that language recognizes a and and in terms of notation we write that a is l of m1 a is the language of m1 so the language of a machine is exactly the set of strings that machine accepts okay so one of the first things we're going to want to be able to do is take a machine and understand what its language is what's the set of strings that that machine accepts another thing we might want to do is given a language build a machine which recognizes that language um so and then understanding what are the class of languages can you get any language from some machine or are there going to be some languages that you can do and other languages that you cannot do so those are the kinds of questions we're going to be asking about these finite automata what kinds of things can those machines do and what can they not do um okay here's our net here is our uh next check-in um so let me um uh so wake up everybody who's not paying attention a check-in is coming um so we have more questions though i can't uh can't keep are these three statements equivalent what to be statements um at the bottom of the slide yes those three are equivalent a is a language those mean the same thing not only are they equivalent but they they're just different ways of saying the same thing um uh that m1 recognizes the language the same as saying that's the language of the machine and that a equals uh that l of m uh that's that's all the same way of saying they all six of one half a dozen over the other it's two ways of saying the same thing okay so let's pop up our poll um and get that started uh whoops still showing the old one oh here we go move it to the next question okay okay so you understand the question here after reason where do we end up after we read one zero one what state are we in do we end up in state q1 q2 or q3 okay go fast this is a okay so i think we got uh pretty much converged here i think uh almost everybody got it right um uh the answer is indeed um that you ended up in state q2 because you go one zero one and that's where you ended up in state q2 so is the mach is this uh string accepted no because you didn't end up in an accept state so this machine rejects one zero one okay um [Music] let's keep going so now um [Music] okay so now we gave it this informal idea of a finite automaton we're going to have to try to get a formal definition now um which is going to be a more mathematical way of saying it's the same thing that i just said um and the reason for having a formal definition is for one thing it allows us to be very precise then we'll know exactly what we mean by a finite automaton and it should answer any questions about what counts and what doesn't count it also is um a way of providing notation um so it'll help us describe finite automata and sometimes there might be an automaton where you know the picture is just too big so you might want to be able to describe it in in in some mathematical terminology rather than by giving a picture or maybe you're going to be asked to give a family of automata where um you know there is going to be a parameter n associated with the uh class of languages you're trying to describe with the automaton and then it'll be more helpful to describe it in this formal notation rather than as a kind of a picture because it might be infinitely many pictures that are being needed um so you may maybe examples of that will come up with now so we'll find out automaton we call it a five tuple don't be put off by that a five tuple is just a list of five things so uh finite automaton will in our definition is going to have five components um it's going to have uh q which is going to be a finite set of states so it's going to be a list you know finite set which will designate as the states of the automaton sigma is the alphabet symbols of the automaton another finite set delta is the transition function that tells us how the automaton moves from state to state those gives it describes how those transition arrows those arrows which connected the states with each other um it describes them in a mathematical way instead of in terms of a picture um and the way i'm doing that is with a function so delta is a function which takes two things so you know i'm hoping you've seen this notation before i'll help you through it once but um this is the kind of thing i would expect you to have seen already so when we have uh q cross sigma so i'm going to give delta a state and an in a state and an alphabet symbol so q is states sigma is alphabet symbols so you're going to get a state and a and a alphabet symbol and it's going to give you back a state so more um describing it you know um [Music] kind of a little bit more detail you're going to you know delta if you give it state q and symbol a equals r that means q when you read an a you go to r so that's the way this picture gets translated into a mathematical function um which describes those transitions and then now q 0 is going to be the starting state so there's going to be that's the one with the in arrow coming in from nowhere and f is the set of accepted accepting states so there might be several there's only going to be one starting state but there might be several different or possibly even zero accepting states that's all legal when we have a finite automaton um and so in terms of using the notation going back to the machine that we just had from the previous slide which i've given you here again let me show you how i would describe this using this notation that comes out of the definition so here is m1 again it's this five tuple where q now is the set q1 q2 group three that's the uh the set of states uh the input alphabet is zero one it might vary in other automata um and f is the set q3 which has only the element q3 because this has just one except state q3 okay um so i hope that's uh helpful um oh of course i forgot the transition function which here i'm describing as a table so the transition function says um you know if you have a q1 and a if you have a state and an input alphabet you can look up in the table where you're supposed to go under the transition function according to the um the uh the state and the alphabet symbol that you're you're given so for example you know if we were in state um q2 um here getting a zero then q2 goes back to q1 so that q2 on zero is q1 but q2 on one here is q3 okay so that's how that table captures this uh this picture okay and it's just a function it's a rep wave representing a function a a finite function um uh you know in terms of uh this uh this table here so i realize for some of you this may be uh slow um we will ramp up on speed but i'm trying to get us all together in terms of the language of the course here at the beginning um okay uh so now um let's talk about some more um uh the computation uh a uh so strings and languages a string a string is just a finite sequence of symbols from the from the alphabet um so don't whenever this class is not going to talk about infinite strings all of our strings are going to be finite um uh there's other mathematical theories of automata and so on that talk about infinite inputs and infinite strings we're not going to talk about that um uh you know maybe rarely we'll make it very clear we'll talk about an infinite string but that's going to be an exception um and a language is a set of strings that's the traditional uh you know um a way that uh uh people in this subject refer to a set of strings they call it a language really because this subject had its roots in linguistics actually um and they were talking about they're trying to understand languages you know human languages um so this is just a historical fact and that's the terminology that stuck okay so two special string a string a special string in a special language um the empty string is the string of length zero this is a totally legitimate string um that you we're going to run into now and then and there's the empty language which is the set with no strings these are not the same they're not even of the same type of object so don't confuse them with one another i mean you can have a a set a language which has just one element which is the empty string that is not the empty set that is a set that is not the empty language that is the a language that has one element in it with namely the empty string okay so those are separate things okay so here's a little bit of a a mouthful here on the slide um defining what it means for a an automaton to accept its input accepts its input string w and we can define that formally and you know it's a little technical looking it's really not that bad um so if you have a your input string w which you can write as a sequence of symbols in the alphabet w one w two dot dot w n so you know like zero one zero zero one i'm just writing it out symbol by symbol here um so what does it mean for the machine to accept um that's that input so that means that there's a sequence of states in the machine sequence of states and of members of queue so these are a sequence from q these are the states of the machine uh that have a certain prod that satisfy these three properties down here first of all and i'm thinking about the sequence is the the sequence that the machine goes through as it's processing the input w so when does it accept w if that sequence has the feature that it starts at the start state each state legally follows the previous state according to the transition function so that says you know the member of the sequence uh is obtained by looking at the previous one the i minus first member of that sequence of that the i the i minus first state in that sequence and then looking at what happens when you take the ice input symbol so as you look at the previous state and the next input symbol you should get the next state that's all that this is saying and this should happen for each each one of these guys and lastly for this to be accepted the very last member here where we ended up at the end of the input so you only care about this at the end of the input you have to be in an accepting state so you can mathematically capture this notion of going along this path um and uh that's what i'm just trying to illustrate that you know we could describe all this very formally i'm not saying that's the best way to think about it all the time but that it can be done and i think that's something you know worth appreciating um okay um so now in terms of again getting back we've said this once already but in terms of the languages that the machine recognizes it's the collection of strings that the machine accepts every machine accepts ex might it might accept many strings but it always recognizes one particular language even if the machine accepts no strings then it recognizes the empty language so a machine always recognizes some one language but it may have many many strings that it's accepting and we call that language the language of the machine and that's the and we say that m recognizes that language these three things mean the same thing okay and now important definition i try to reserve the most important things or the highlighted things to be in this light blue color if you can see that we say a language is a regular language if there's some finite automaton that recognizes it okay so there are going to be some languages that have associated to them finite automata that actually solve those languages that recognize those languages but there might be other languages and we'll see examples where you just can't solve them you can't recognize them with a finite automaton those languages will not be regular languages the regular ones are the ones that you can do with a finite automaton that's the traditional terminology okay so let's continue let's go on from there so look a couple examples here again is that same getting getting to be an old friend that language that automaton m1 uh remember its language here is the set of strings that have the substring one one that is the um that language a now what do we know about a from the previous slide think with me don't just listen a is a regular language now because it's recognized by some automaton so all of the whenever you find a um an automaton for a language a finite automaton for language we know that language that language is a regular language so let's look at a couple of more examples so if you take the language let's call this one b which is the the strings that have an even number of ones in them so like the string one one zero one would that be in b no because it has an odd number of ones so the string one one one one has four ones in it that's an even number so that string would be in b the the zeros don't don't matter for this language so that string um this of of of strings that have an even number of ones uh that's a regular language um and the way you would know that is you would have to make a fine art automaton that recognizes that language and i would encourage you to go and make that automaton you can do it with two states it's a very simple automaton but if you haven't had practice with these i encourage you to do that and i actually there are lots of examples that i ask you to solve at the end of chapter one in the book and you definitely should spend some time playing with it if you're not if you have not yet seen uh finite automata before um you need to get comfortable with these and be able to make them uh so we're going to start to we're going to start making some of them but we're going to be talking about it at a sort of a more abstract level in a minute um uh basically the reason why you can you can solve this problem you can you can make a fine art automaton would recognize is the language b is because that finite automaton is going to keep track of the parity of the number of ones it's seen before this has two states one of them remembering that it's seen an odd number one so far or the other one remembering it's seen an even number of ones before and that's going to be typical for these automata finite automata there's going to be several different possibilities that you may have to keep track of as you're reading the input and there's going to be a state associated with each one of those possibilities so if you're designing an automaton you have to think about as you're processing the input what things you have to keep track of and you're going to make a state for each one of those possibilities okay so you need to get comfortable with that um let's look at another example um the language c where the inputs have an equal number of zeros and ones that turns out to be a not a regular language um so what in other words what that means is there's no way to recognize that language with a finite automaton you just can't do it that's beyond the capabilities of finite automata and that's that's a problem that's that's a statement we will prove later um okay um and our goal over the next uh lecture or so is to understand the regular languages which you can do in a very comprehensive way um so we're going to start to do that now so first we're going to introduce these this concept of regular expressions um which again these are things you may have run into in one way or another before um so if we have a uh um we're going to introduce something called the regular operations now uh you know you i'm sure you're familiar with the um the arithmetical operations like plus and times um those apply to numbers now the operations we're going to talk about are operations that apply to languages so they're going to take let's say two languages you apply an operation you can get get back another language like the union operation for example that's one you probably have seen before um the union of two languages here is a collection of strings that are in either one or the other um so but there are other operations which you may not have seen before that we're going to look at um the concatenation operation for example so that says you're going to take a string from the first language and another string from the second language and stick them together and it's called concatenating them and you do that in all possible ways and you're going to get the concatenation language from these two languages that you're starting with a and b the symbol we use for concatenation is this little circle but sometimes we don't often we don't we just suppress that and we write the two languages uh next to one another with the uh little circle implied so this also means concatenation over here just like this does and the last uh last of the regular operations is the so-called star operation which is a unary operation that applies to just a single language and so what you do is now um you're going to take to look get a member of the star language you're going to take a bunch of strings in in the original language a and you stick them together any number of members of a you stick them together and that becomes an element of the star language i will do an example in a second if you didn't get that but one important element is that when you have the star language you can also allow to stick zero elements together and then you get the empty string so that's always a member of the star language the empty string okay so let's look at some examples let's let let's say a is the language these are two strings here good bad and b is the language boy girl okay now if we take the union of those two we get a good bad boy girl that's kind of uh what you'd expect um and um if uh um now let's take a look at the concatenation um now if you concatenate the a and the b language you're going to get all possible ways of having an a string followed by all possible ways having a b string so you can get good boy good girl bad boy bad girl um now uh looking at the star um [Music] well that applies to just one language so let's say it's the good bad language from uh a uh and so the a star that you get from that is all possible ways of sticking together the strings from a um so for there are no using no strings you always get the empty string that's always guaranteed to be a member of a and then just taking one element of a you get good or another element bad but now two elements of a you get good good or good bad and so on um or three elements of a good good good bit good good bad and so in fact a star is going to be an infinite language if a itself is um uh contains any non-empty member so if a is the empty if a is the empty language or if a contains just the language empty string then a star will be not an infinite language it'll just be the language empty string but otherwise it'll be an infinite language i'm not even sure okay uh i'm not i'm ignoring the chat here i'm hoping people are getting are you guys getting your questions answered by rtas how are we doing thomas uh one question is are the supplies going to be posted are the slides going to be posted well um uh the whole lecture is going to be recorded um is it helpful to have the slide separately i can post the slides um sure i'll remind me if i don't but i'll try to do that yes it is helpful i will i will do that um yeah um yeah i will post the slides just thomas it's your job to remind me okay um [Music] all right good uh so regular so we talked about the regular operations let's talk about the regular expressions so regular expressions are just like you have the arithmetical operations then you can get arithmetic expressions like you know one plus three um times seven so now we're going to make expressions out of these operations first of all you have the more atomic and things the building blocks of the expressions which are going to be like um uh elements of sigma you know elements of the alphabet or the sigma itself as as an alphabet symbol or the empty string or the empty language of the the empty empty language or the empty string these are going to be the building blocks for the regular expressions we'll do an example in a second and then you combine those those basic elements using the regular operations of union concatenation and star so those are the these are the atomic expressions these are the composite expressions so for example um if you look at the expression zero union one star so that we can also write that as sigma star because if sigma is zero uh and one then sigma star is the same thing as zero union one is sigma is the same as zero union one and that just gives all possible strings over sigma so this is something you're going to see frequently sigma star means all pos this is the language of all strings over the alphabet we're working with at that moment now if you if you take sigma star one that's gonna you just concatenate one onto all of the elements of sigma star and that's going to give you all strings that end with a one you know technically you might imagine writing this with braces around the one but generally we don't do that we just single element sets single element strings we write without the braces because it's clear enough without them and it gets messy with them so sigma star one is all strings that end with one or for example you take sigma star one one sigma star that is all strings that contain one one and we already saw that language once before that's the language of that other machine that we presented on you know one or two slides back okay um right uh yes so um uh yeah but in terms of readings by the way sorry to i don't know if it's helpful to you for me to do these interjections but the readings are listed also on the homework so if you if you look at the posted homework one it tells you which which chapters you should be reading now and also if you look at the course schedule which is also on the home page it has the whole course plan and which readings are uh for which dates so it's all it's all there for you um and so our goal here this is not an accident that sigma star one one sigma star happens to be the same language as we saw before from the language of that of that finite automaton m1 um in fact that's a general phenomenon anything you can do with a regular expression you can also do with a finite automaton and vice versa they are equivalent in power with respect to the class of languages they describe and that's one we'll prove that okay um so you know it's got you know if you step back for a second and just let you let yourself appreciate this it's kind of an amazing thing because fine at automata with the states and transitions and the regular expressions with these you know operations of union concatenation and star they look totally different from one another they look like they have nothing to do with one another but in fact they both describe exactly the regular languages the same class of languages um and so it's kind of a cool fact that you can prove that these two very different looking systems actually are equivalent to one another um can we get empty string from empty set yet there are a bunch of uh exotic cases by the way so empty empty language star is the language where has just the empty string if you don't get that chew on that one that means but that is a that is that is true um uh okay let's move on okay let's talk about closure properties now we're going to start in doing something that has a little bit more meat to it in terms of we're going to have our first theorem of the course coming here and this is not you know it's not a baby theorem this is actually uh there's going to be some meat to this and you're going to have to uh um you know you know it's not totally um this is not a toy this is we're proving something that has a real substance and and the um uh the statement of this theorem says that the regular languages are closed really the class of regular languages are closed under union closed under the union operation um so what do i mean by that so you you know when you say a uh collection of objects is closed under on some operation that means applying that operation to those objects leaves you in the same class of objects like the you know the um the natural you know the the positive integers the natural numbers that's closed under addition because when you add two you know positive integers you get back a positive integer but they're not closed under subtraction because you know 2 minus four you get something which is not a positive integer so close means you leave yourself in the collection and the fact is that uh if you look at all the regular languages these are the languages that the fine automata can recognize they are closed under the union operation so if you ta you start off with two regular languages and you apply the union you get back another regular language and that's what the statement of this theorem is i hope you can i hope that's clear enough in the way i've written it if a1 and a2 are regular then a1 union a2 is also regular that's what the statement of this is and it's just simply that um that's proving that the class of regular language is closed under union so we're going to prove that so how do you prove such a such a thing so you know the way we we're going to prove that is you uh start off with you know what we're assuming so we're our hypothesis is that we have two regular languages and we have to prove our conclusion that the union is also regular now the hypothesis that they're regular you have to unpack that and understand what it what is that what does that get you and them being regular means that there are finer automata that recognize those languages so let's give those two fighter automata names so m1 and m2 are the two finest automata that recognize those two languages a1 and a2 that's what it means that they're regular that these automata exist so let's uh have those two atomic m1 and m2 using the components as we've described this you know the respective state sets input alphabet transition functions the two starting states and the two collections of stepping states here i'm assuming that they're over the same alphabet you could have automata which operate over different alphabets it's not interesting to do that it doesn't add anything the proof would be exactly the same so let's just not over complicate our lives and focus on the more interesting case so assuming that the two input alphabets are going to be the same um and from these two automata we have to show that this language here the union is also a regular language and we're going to do that by constructing the automaton which recognizes the union that's really the only thing that we can do um so we're going to build an automaton out of m1 and m2 which recognizes the union language a1 union a2 and the task of m is that it should accept its input if either m1 or m2 except and now what i'd like you to think about doing that how would how in the world are we going to come up with this find out automaton m um and uh uh the way we do that is to think about um how would you do that union language you know if i ask you i give you two automata m1 and m2 and i say here's an input w um are is w in the union language that's the job that m is supposed to solve and i suggest you try to figure out how you would solve it first i mean this is a good strategy for solving a lot of the problems in this course put yourself in the place of the machine you're trying to build and so you know if you want to try to figure out how to do that you know natural thing is well you take w you feed it into m1 and then you feed it into m2 and if m1 accepts it great and you know it's in the union and if not you try it in and try it out in m2 and see if m2 accepts it um now you have to be a little careful because you want to have a strategy that you can also implement in a fine art automaton and uh and a fine art automaton only gets one shot at looking at the input you can't sort of rewind the input you feed it first into m1 and then you feed it into m2 and uh operate in a sequential way like that that's not going to be allowed um in the way uh a finite automata work so you're going to have to be a little bit more take it to the next level be a little bit more clever and instead of feeding it first into m1 and then and then into m2 you feed them into both in parallel so you take m1 and m2 and you run them both in parallel on the input w keeping track of which state each of those two automata are in and then at the end you see if either one of those machines is in an accepting state and then you accept so that's the strategy we're going to employ um in building the finer automaton m out of m1 and m2 so here's in terms of a picture here's m1 and m2 here is the automaton we're trying to build uh we don't know how it's going to look like it and uh yeah so kind of getting ahead of myself but here is the strategy as i just described for amp um we're going to keep track m is going to keep track of which state that m1 is in and which state m2 is in at any given moment as we're reading the symbols of w we're going to feed it also into m1 and also into m2 and so the possibilities we have to keep track of in m are all the pairs of states that are in m1 and m2 because you're going to really be tracking m1 and m2 simultaneously so you have to remember which state m1 is in and also which state m2 is in and so that really corresponds to a pair of states to remember one from m1 and one from m2 and that's why i've indicated it like that so m1 is in state q m2 is in state r at at some given point in time and that's kind of correspond to m being in the pair q comma r that's just the label of this particular state of m that uh we're gonna apply here okay and so um and then uh am is going to accept if either m1 and m2 so is an accepting state so it's going to be if either q or r is an accepting state we're going to make this into a an accepting state too okay whoops there we go um [Music] so let's describe this formally instead of by a picture because we can do it both ways and sometimes it's better to do it one way and sometimes the other way so now if we take uh the components of m now are the pairs of states from m1 and m2 again i'm writing this out literally uh explicitly here but you should be make sure you're comfortable with this cross product notation so this is the collection of pairs of states q1 and q2 where q1 is in the state of the first machine q2 is the state of the second machine the start state is you start at the two uh start states of the two machines um so this is q1 q2 probably i should have not reused the q notation i should have called these r's not of them looking at that but anyway i hope you're not confused by reusing this q1 and q2 here are the specific start states of the two twos of the two machines these are just two other states representative states of those machines now the transition function for the new machine is going to be built out of the transition functions for the old previous machines so when i have a pair qr and i have the symbol a where we go which new pair do we get well we just update the state from m1 and update the state from m2 according to their respective transition functions and that's what's shown over here um now let's take a look at the accepting states for m the natural thing to do is look at the set of pairs of states where we have a pair of states of the pair of accepting states one from um the first machine and one from the second machine but if but if you're thinking with me you realize that this is not the right thing what is dfas uh did i recall them dfa somewhere oh somebody else is probably doing that in the chat uh the dfa you careful what notation you're using we haven't introduced dfas yet uh we'll do that next on thursday uh but these are dfas these are just fine at automata deterministic finite automata that's why they're why the d anyway so this is actually not right because if you think about what this is saying it says that both components have to be accepting and you want either one to be accepting so this is not good this is a this would be the wrong way of defining it that actually gives the intersection language and really kind of along the way it's proving closure under intersection which we don't care about but might be useful to have in our back pocket sometime in the future um in order to get closure under reunion we have to write it this slightly more complicated looking way which says that you know uh the pair what you would want to have is either the first state is a an accepting state and then any state for the second uh element or any state for the first element and an accepting state for the second element that's what it means to have the union uh to be doing the union okay so let's let's do uh oh here's a quick check in um [Music] so let's let's do another poll here you thought we we thought we were done with these um again you know oh here we go so i i it was too complicated to write it out in the poll so i actually put it up on the slide for you um [Music] so i'm all i'm asking is that m1 has k states k1 states and m2 has k2 states how many states does m have is it the sum the sum of the squares or the product okay you have to think about what are the states of m what do they look like um and uh come on guys all right ending the poll uh sharing results yes indeed it is most of you got it correct it is c the the product because when you look at the number of pairs of states from m1 and m2 you need all possible pairs and so it's the number of states in m1 times the number of states in m2 so make sure you you understand that and think about that um to uh to so that you're you're following um and and and get this all right so um let's move on here so we have another five minutes or so let's start thinking about closure under concatenation so if we have two regular languages so is um the concatenation language um we're gonna try to prove that we won't finish but we'll at least get our creative juices going about it um so we're gonna do the same scheme here we're gonna take two machines for a1 and a2 and build a machine for the concatenation language out of those two so here are the two machines for a1 and a2 written down um [Music] and here is now here is uh the concatenation language and i'm going to propose to you a strategy um which is not going to work but it still is going to be a good intuition to have so what i'm going to do is i'm going to make a copy of m uh okay let's understand what m is supposed to do first so m should accept its input so think about this m is doing the concatenation language so it's given a string and it's an answer is it in the cat concatenating the concatenation language a1a2 or not so it should accept it if m1 if there's some way to divide w into two pieces where m1 accepts the first piece and m2 accepts the second piece uh so the here would be the picture okay and now um we have to try to make a machine which is going to solve this intuition so how would you do that yourself you're giving you w and you can simulate m1 and m2 so the natural thing is you're going to start out by simulating m1 for a while and then shift into simulating m2 for a while because that's what happens as you're supposed to happening as you're processing the input so i'm going to suggest that in terms of the diagram like this um so we have here um uh m1 and m2 copied here uh and what i propose doing is uh connecting m1 to m2 so that when m1 has accepted its input we're going to jump to m2 because that's perhaps you know the first part of w and now we're going to have m2 process the second part of w so the way i'm going to implement that is by declassifying the start state of m2 having transition symbols from the accepting states of m1 to m2 and then removing these guys here as uh accepting states and we have to would have to figure out what sort of labels to apply here but actually this reasoning doesn't work it's tempting but flawed because what what goes wrong what happens is that you know it might be that when m1 has accepted an initial part of w and then it wants m2 to accept the rest it might fail because m2 doesn't accept the rest and what you might have been better off doing is waiting longer in m1 because there might have been some other later place to split w which is still valid splitting w in the first place where you have m1 accepting an initial part may not be the optimal place to split w you might want to wait later and then you'll have a better chance of accepting w of accepting w so um i don't i don't know sure if you quite follow that but um uh in fact it doesn't work the question is where to split w and uh it's challenging because how do you know where to split w because it depends upon what you it's a it might it depends on why and you haven't seen why yet so when you're trying to think about it that way it looks hopeless but in fact it's still true and we'll see how to do that on thursday so just to recap what we did today um we did our introductory stuff we defined fine art automata on regular languages we define the regular operations and expressions uh we showed that the regular languages are closed under union we start a closure under intersection to be continued you