now just to recap what we’ve talked about in the past we’ve talked about regular languages context-free languages context sensitive languages and recursively enumerable languages and when we put these all together we want to make like one big picture out of this there’s a famous professor at MIT Chomsky and he’s a natural language professor not a computer science major you know natural languages like English and he did a lot of study on this and there’s a big overlap between what we’re studying in this course and natural languages so just do my kind of a high-speed review of what we’ve talked about an example of a regular languages is a language that can be accepted by a finite automata so here’s just kind of a random language this is language where you have to the work has to start with an A and then for as many times as you want it could be followed by a B a and then another P a and another BA so if we were to create a finite automata for it we would have a start state and if we read an A we go to a state that we are calling a yes a painting if we end up in this state will answer yes and we end up in any of these states will answer now so if the first thing we read is a B that’s no good because it has to start with an end so if we read a baby don’t – this is what we sometimes call it trap see if you ever get into this state and then any of these you just stay you’ll never answer yes so if you ever get into the state the answer will always be nothing but if we read the name go to state that says well okay this is an acceptable word now if we read a B after it we go to state that says it’s no good but if we read a be followed by a that we’re back to being good again right because this language where we have an a and then an infinite series of bees followed by days so we can be than any then we go be a be any be do this red if we do anything other than that we’re going to slide into this state state you so this is a finite automata for that language so every language has a corresponding grammar to it and if you think about it the grammar would basically be we have start like maybe this is the best state we start here and then we have to see something that takes us to another state and then we’ll come up with a symbol for this state so what we’re going to do is we’re going to have a grammar will call this as a start state and then this state will be the X just randomly pick up letter X meaning I’m an a state and they don’t describe to find a mistake what do I need to see to be an acceptable work to eventually go out to to a yesterday so the corresponding grammar for this language would look like this we would start at the basically start state if we see an a we come we’re kind of moving to another state and then from that point what do we need to see well what we don’t need to see is a B and then a welcome first of all we could read the name and then see epsilon which is stuff that’s the entities or we could read a be an a and then we’re right back in the same state we were in so what I wanted to point out is that this grammar of Correspondence do this to this state machine so this is basically we’re starting in state X we require that we see in any and then this is I’m sorry this estate s we require that we see an a and then we’re calling this state X and then as long as you see it be in the day and being the name uses we want what we can just stay here meaning we’ve read nothing that would be the epsilon those are considered acceptable words if you see anything else we’re going to consider it in the we’re going to answer no so this this is kind of like the intuitive looking at the picture and writing the grounded us but we could consolidate it into a 1:1 graph we could say we start with a word and it’s either a knee or something acceptable followed by a VA and the only thing acceptable would ever be an A or a B a with a name with a VA so this is a grammar that all so anytime we have a grammar where our big symbols of the big symbols basically grate down into little symbols and eventually it goes to these letters and if all of the little letters are on either the left

side or the right side of of these letters that glama would that be considered regular if there are symbols that have to be on one side of a big lettering and the other symbols on another side that’s going to be a higher-level language okay yeah this is going to come up a little bit later if you remember we talked about recursively enumerable languages there is the concept of we could have a language that we can enumerate so we wanted to print down all the words that are in this language we can write an enumerated program and what we basically do is we call the program of the string of s and we print out an A and then we take s and we concatenate a v8 on the end and we call the program again and it’ll print out an ABA and then here another being and call it self again so here we would be recursively printing out recursively and numerating the entire language and we can call it with a man to start with so we call the enumerator and let it run now this was run forever right because we just keep concatenated concatenated a ba onto the end of the last thing we printed and print that one out so we are recursively enumerate in this language so we say that this language you notice is a regular language we can also say this is a recursively enumerable language meaning we can write a recursive program that can print out every word in the language ok that’s going to be important enough to understand a little later we’ll talk about higher levels of languages ok just a couple of properties for now regular languages are a finite state automata can decide the language meaning it will always if you give an input word and you’re asking yes or no is this in the language we can build a finite automata that doesn’t use any memory and we’ll always answer yes or no for all all inputs and it’s also either left or right linear clamor that exists for that language so this is kind of the simplest form of languages ok then if you remember we moved to the next topic which was context-free languages so this was a language where and I probably does symbol as the most popular example is the aim of the IP DS that means the number of A’s and the number people each other and the only way we think we talked about this when we talk about context-free languages we said the only way we could build a state machine that can answer yes or no for all possible inputs that somehow you had to count up how many aids there are and then make sure the count of the bees match now we had one memory cell that was allowed to go as high as infinity we could solve this right so what we do is we would start in the state who say if we read a name we would add one to the counter and then we’d have to read a corresponding B and and minus one from the campus over the counter hit zero but a piece of memory that it’s actually takes a little you know a little thinking less less less having less computing ability would be a step where you’re actually you can as we read symbols we can push the symbols onto the stack and we’re only allowed to read or or access the top of the stack we’re not allowed to read all the storage in it the stack could actually be considered a state we can actually even multiply though the values on the stack and come up with a number that represents the content of the stack so a stack is much less computing has much less computing power than one memory cell that can go off to infinity so if we have a language where we’re going to bounce around from state to state and we have the ability to push and pop off of a stack we could write an automaton that uses a stack to answer yes or no to all possible implicit this language so if we started a state and then every time we see in pain we push and hang on to the stack if we see another would push another and we push another right we keep doing that and we’re basically pushing it onto the stack and then what we have to finally see some B so we read of B we pop any off the stack and we go to this state that’s we’re pulling a guest state but there’s nothing condition here we could

continue to read these and keep popping the stack and if we read anything out of line we go into this trap state where we’ll always answer now after we have read the entire input if we are in the state of yes and another condition the stack must be empty then we can officially answer yes before the S state but there’s still stuff on the stack what that basically means is we read more as than B’s so will answer no so we have a finite state machine that every time we read an input we may read or access the stack we may not that’s our choice and we have to end up in a guest state and we have the right conditions about the stack so in this case the stack would have be for this to be a language that is for this to answer yes or no to any word in that language so the same language has a grammar that goes like this we have a start value an acceptable value which would be in vanity for any word that has been accepted before within a in front of it and the be after so for example a tea is good and then a maybe be just good and then a what we just had before they followed by because someone was really one line is the camera for this language but what’s being captured here because every day must have a corresponding B is going to require more than just a state machine it’s going to require some kind of memory and the memory of a static is plenty to solve this and the stack like to say is very there’s a very limited very limited piece of memory equipment as we go on through this hierarchy we’re going to add more mental okay so and you know I was just doing this to show that we could personally don’t worry at this length we start with though we call this the avian in brain would start with a blank and the string s comes in was put an A in front of it of ten capital P after it and we print it out and then we call it again and it puts an A in front of that input and at the entrance and little prick that this program will print out ad than AAA BBB AAA BBB and just go on forever so we can recursively enumerate this line okay properties of context-free languages is the languages are decided by a finite automata with a stack which is also known as a push down with tongue and we can express it can be expressed with context-free language context-free grammar that’s where the big symbols like the big s can be written as small symbols with a big symbol between them but symbols can be on either side of them they don’t have to be linear or rightfully so and that’s basically keeping track where what the stack can handle okay so now this is just like this is a very small version of the English language just to capture the idea of what parsing the languages so we have a start symbol this is kinda like our big ass when we say a sentence is the subjects followed by a predicate and this okay what’s the definition of a subject so we’re breaking down we’re basically taking like as input let’s say in English sentence and ask ourself ESOL does this sentence belong in the English language they say okay we start with a sentence while the sentence has the first part in second part and then we describe the first one and the first part is punched back to Penta kids followed by subject and maybe in other adjectives so this is like a left left linear parameter and then eventually it could be a noun then we have a predicate which describes what the man was doing and we can have an adverb followed by project another adverb another adverb when we eventually have a burger and then examples of adjectives could be like brown big etc and adverbs could be loudly or quietly now it’s gonna be like a dole or a person verbs can be like bog or spoke so this is but this is not the grammar for the English language is a subset of being exclaims there are other sentences that allowed if we were to and I just wanted to go over an example in English just so the show that we’re doing something very similar if we were to parse the big round goal of bark loudly bark we’d say is this a sentence well maybe it is maybe this does it start with a subject and then with a predicate okay that depends let’s break down what a subject is well so that can be the followed by a subject because we said it could be an adjective followed by

a brand-new something under qualified credit so the big says the subject which was big ground at this point became big followed by Brambilla and then the king became big round abdullah followed by subject and then the big round don’t follow my hand and then it was so we now had this officially important to a subject now we’re trying to see if what follows that is pregnant and there’s a big grass dog and then bar followed by predicate and then the big brown dog laughs loudly followed by a verb and then like I should have had this actually should have been loud yeah that should be right and then eventually we say yes so we ran it through a parser and so it kind of looked like we wrote this this is a simple version thing this language but this is actually a regular language because we decided that all the adverbs and adjectives are on the left side of the names of verbs which is not required in the real English language so it’s not you know I’m just doing that kind of to make a point okay so now we’re going to move on to we’ve talked about regular languages and context-free languages now let’s look at a more interesting language let’s take the language where the number of A’s is equal to a power of two okay so for example a a is in the language two A’s forays AAA 8 8 16 names but all the other ones are now 11 and let’s say the whole alphabet for this this language is just the letter A okay so as this can we can we create a finite automata maybe with a stack that can print these out or do we need like more equipment so the first thing we ask ourselves is it can we even enumerate the language okay so this will be the powers at a to the power two range well we can take a language and on the right okay so we can take a letter like pay and then we say okay take a as input concatenate and payment so we have a a printed out a and then we call the program began with a a is so now we think AAA and AAA which is stories print that out pull them in with Forex now we have four days and for it says eight names I don’t know so we can enumerate this language know almost all languages can be enumerated recursively already printing out the results but now this question is how would we build this language so let’s look at it from a grammar point of view first but sometimes the grammar the grammar sometimes gives us the insight to the equipment we need which is like a state machine and maybe some memory and sometimes the state machine gives us insight to what the grammar is so this is a kind of a confusing grammar I remember when I first saw this I spend a lot of time with it but here’s what we’re basically doing well this one was saying is we’re starting with an S and then seeing if it can break down into smaller parts till we finally we can finally answer yes or no so what’s really happening is he has these big symbols a and B a phase a marker for the beginning of the word beads a marker for the end of the word and then inside the word we either have two A’s or four days or eight days and so on and these are the rules that check that we get there so what we’re going to do is we’re going to have this letter C go sliding through all the eggs and we start up with 111 hop over all the A’s and every time it sees it’s been a doublet turning it to two days so when we see a seat on buying any we turn it into two A’s and push the sea after so basically the sea is going to go from starting at a and E and B every time it’s season a it turns it into two days okay so every CA turns into two two ways with the sea anchor so if we had eight days here with a cd4 T do when Scannell v8a is we turned them into sixteen eight as it was hopping over then and then when it finally when the sea gets to the be a see right before a B well we want to take the big letters C and slide it back to the egg and then go and double them

all again so we can turn and become a see a a see right before B that means we’ve done for the end of the word turning to a D and then have the d hop over wall DA’s until it gets back to be a and then go through the string again mm all the AIDS so basically if those like the kind of which had the market right now but if we had an egg followed by eight I’m sorry we had an a a big a followed by a big C followed by eight eight the sea would hop over each a turning them into two 80s so by the time it got the negative 16 A’s and then we would change the Stevie DeeDee and all of DP that was a CP to a DV and then the D would be after all 16 A’s and the D can just hop across what it is leaving him alone so Amy’s become das meaning for just popping the D over the back till we hit the beginning again when we get to the beginning we change the D to a C and then it’s not hopping across all the a is doubling them again and then eventually we want to say we’re ready to stop so eventually one of the C marker gets to the B we turn it into an E and an a followed by a BB comes to be followed by an egg so that market goes back to the beginning until it lines up with the capital n E and that becomes an Epsilon so it’s a little confusing how this grammar works but the issue is this this grammar of will take anywhere that has a power of two of a z’ and answer yes or no now what’s interesting about this grammar and this is really where we get into the concept of this is kind of an important concept whether a language is guaranteed to be to always answer yes or no in this language these are symbols all of these are symbols a see little a and Big B the big symbols can be broken up into other stuff the big sin will get converted into love it if every times kind of life so this is kind of important content – this english-language example if a sentence breaks down into small parts of that each of these small positive broken down into each time they do a breakdown that these suddenly apply one of those rules of the languages if it breaks down into stuff that’s bigger than previous time we’re going to eventually get to these words the little the words of the language and that not symbols that mean a couple of those words will eventually get down to individual words and it will stop but if any of these rules say if any of these rules say like a predicate and subject could turn into one thing then we’re not always getting wider and getting to an answer yes we could have we could have so for example we we could have this one symbol turns into four symbols but these two symbols become one simple so what were what were parsing could get bigger and smaller and bigger and smaller and bigger and smaller and we may go on forever when I couldn’t get bigger and bigger and bigger until we matched the input work we could get into an infinite loop but we’re getting bigger and smaller and bigger and smaller so we made a rule that said all productions all of these rules these four productions have to have a property that we never have I put the two highlighted the two that don’t follow this property if we said that all productions the number of symbols have to equal the number of symbols on the right side has to be at least as many as those on the left side then we can never make the word gets smaller than bigger than smaller than bigger and possibly go into an infinite loop so if we say we can write a parameter for a language and we say we say that a language that has these two problem productions we call this an unrestricted grammar and what this basically means is that it is possible if we allow productions like this it’s possible for us to start parsing a word and never actually get where we have just letters and media in the language we could get stuff in

reduction so okay so now what I thought we’ll get back to that kind of language in a second now I just want to talk about the compliments of my friends okay so this is now once again we’re back on the topic of enumerated language suppose we wanted to have the language all the words that are any combination of our alphabet so our alphabet is A’s and B’s and we want to print that every possible combination so I’m creating out the universal set so what we’re doing is we’re saying print that every combination of A to B so we write an enumerator that takes its input nothing like concatenates and a onto the end of it prints it out contending for bienvenue prints it out and then recursively calls itself with the any word should be sorry that should be B word that’s the B word and that will recursively print down to a a Navy VA a BP and then all of these words with that pain on the end of them and all of these words with Abby Montana which would be over these and I’ll just go on and on forever and it’ll eventually print out the entire every combination of every word that could be made with the letters of a and B now suppose we wanted to print the compliment of a language so suppose we had all the words such that they are not words where it’s a bunch of a DS followed by a bunch of bees and the numbers max over than what all the words that are in other words when all the words found in this line so that would be kind of like printing out the universal the universal said but don’t print out the ones where only print out the ones that are not members of this language so we you know be the same cause before again this should be SP but now as you generate then we say if it’s not in the AI bi language which we built to find out a commoner with a stack earlier we can check that off it is so we’re just calling that routine and then we print it so well basically the numerating every word we could make out of A’s and B’s but we’re skipping the ones that meet the condition the number of bees equal each other so it’s the same amount as last time except the a a and the B PMSing these are all fine because they’re an odd number of letters so we can we can enumerate a language and we can enumerate the complement of the language okay so that was just a side thing I wanted to throw in because that this is gonna all might kind of come together if it all out battle productions if we say that what’s on this side so this is maybe a bunch of a bunch of symbols here becomes a bunch of symbols yet we make a rule that says the beta side is as big or bigger than this side then we will be guaranteed as we’re taking word as input and parsing it will eventually get bigger and bigger and bigger and the size of all our symbols will equal the input word and we can stop well we got if we produced a word bigger than our input symbols that we know we’ll never get we’ll never string down and that’s the input symbol so we can so know so if you follow this rule for grammar that the right side has as many symbols or more than the left side then we will always be guaranteed to let the program run and eventually answer yes or no for all inputs in Atlanta a yes or no will never go into an infinite loop okay so a recursive language is this a new definition it’s a language where we can build a finite automata machine with some memory so now this is when I say some memory what another class were talking about that touring machine but right now I’m saying some kind of memory maybe a stack maybe even more but if we can build a finite at Agra with some memory and for all possible inputs we can always answer yes or no will never go into an infinite loop we’re going to call that a recursively and then all the languages that are have a restrictive grammar meaning the beta side is as big or as big as the Alpha side those are restrictive that restrictive languages and we’re going to pull those this new name something sensitive

language so those a context sensitive languages on languages that will always produce a yes or no ok now languages that are recursively enumerable so I’ve shown throughout this throughout the slide that showed many languages and have recursively a memory so we have a language and we say is this thing recursively enumerable all you have to do is be able to write a program that could just recursively spit out every member that doesn’t mean you could recursively ignore it but complement of them but if you can print that if you can write a program that can enumerate all of the members of the language which would be all the things we would answer a yes – then that’s a recursive language if you try to enumerate everything that was and answer no it may go into an infinite loop it’s still recursive as long as we can answer yes for members as as long as we can answer yes for members or recursively numerate the entire language it’s considered a recursively Xin will point to an example of one an example of the language that is recursively enumerable but its complement is not recursively enumerable is the famous halting problem right so so for example now what if a language what if a language is we could recur suppose we could build some piece of equipment that could recursively enumerate a language in other words print out every member of of the language and then suppose we could recursively enumerate its complement we could print out everything that’s not in the line like just before we wrote a program that will print out every string that is not a number of a is followed by a number of beads where the numbers match every string that doesn’t need that image so suppose we could write a program that can print them every member of a language and then a separate program that prints out every member that this is a l complement that can get get a bar across the top so this means to complement about so we could recursively enumerate the complement meaning print out every member that’s not in the language then could we build a machine that always answers yes or no for that language and we could by doing a time-sharing sum up as well as a dovetail let’s say we wanted to know is the word a be a eighth in the language where the number of A’s and the number of bees equal each other this program which is spitting out every word in the language so this program it’s a AAA BBB AAA BBB AAA BBB this is printing a todos this language princess everything that’s not in this language so this is going to print down a B a a a B be a B not B you know all the all the words that are not in this language eventually one of these two machines that’s in the printing at Woolworth’s in the language for printing at all horses not the language eventually one of them bring this thing out right so we wrote this to say instead of printing that now compare them to this and if they match answer yes so this they can recursively generate all the members of the language and this thing can recursively generate all the members not in the language eventually one of these two machines is going to match this and if this one finds a word that matches this and have this thing answered now so this is kind of the overall design this is the overall design of a machine that pops up now the other thing that’s fun sharing part what we’re going to do is we’re going to write some code that said okay let this one run for a little while like five minutes and do that forever eventually one of these is going to go up family and if this one finds that it’s going to spit out a yes and if this one no but any word we put in this machine we will always be able to answer yes or no and neither one of these goes into an

infinite loop will always be able to answer yes so what we’re saying here is if a language and its complement can be recursively enumerated if you can print out every member of the language and every member of the complement then that language there’s a special word means it’s recursive we could write a recursive function that could always answer yes or no and the other thing we could do we could recursively like that example we’re at the universal anova numerated recursively enumerated the universal language we could do that and then just ask ourselves over here are all these here so we could doesn’t make this language rehearsal to anything so this is uh this is I wanted to make I wanted to make so all languages that are regular languages that can be answered yes or no with a finite time and if you put if you put in input work and we run our test we will always answer yes enough context so one of these three to be green and this one to be red so the words that are context-free languages that if you give an input word we get to create a state machine plus make use of the stack and we can always answer yes or no if it’s a member of the language context-sensitive were words now this is where we said as long as all the production’s in the grammar never shrink so we basically said it’s all production anything anything that’s on the right side has to be as big or bigger than what was on the left side so as we’re building words in the language of testing words we never get small and we will eventually grow big enough to match the size of but and will either answer yes a moment we have a grow bigger than four if we’re generating words following the rules of the language and we grow bigger than the input word we will never shrink back down and match their footwork if we were all past it we’re done the answer is not so for context fruits are context sensitive languages we can always answer yes or no and they have that rule that the productions that was on the beta side or the right side has to be as bigger bigger than what’s on the left side and what that translates into is the equipment we’re going to use for convex sets of languages is a state machine and a chunk of memory that is linear in size to the implement word and will never be in a situation where it grows so grows bigger than a linear bound on the input word and make its way to ring his way back down to people work so in this case of a context-free case using a stack in this case we’re using kind of like a stack but we get to look at all the contents of the stack so it’s really like a linear piece of memory that is linear in size to the input so when all three of these cases we will always be able to answer yes or no for any possible ranges you can give so that what that means is in all three of these cases we can recursively enumerate the language and we can recursively integrate that complement the blind for any language that’s in this what should be the green circle and then the question was they almost immediately you think the whole world is in this it’s it possible that we could dream up a language that says that says you know we built up some machine a state machine and some memory and then you start processing the word we’re trying to answer yes or no is it in the language and that’s what processing it now we go outside of this where we don’t have that restriction that all productions have to go production production is it possible that we dream up a question where instead of answering yes or no for some inputs we can actually end up looping forever and that’s the one that Tory came up with your question is a halting problem is an example where again you

know we review the lecture on recursively enumerable languages but the idea was if you had a program and you gave it an input with that program going to an infinite loop or what it stopped and the answer to that question is and so you’re taking it as input the program and its input and you’re asking will it stop will it solve this whole new problem well if multiple go into an infinite loop and Tory proved nobody could ever write a program that would answer yes and no for all possible inputs you could argue that you can answer the yes on the yes side you could enumerate them by taking every possible program and every possible input and if it halls spit out yet smaller but the ones that don’t want will just look for it so that was one example in mathematics so so these four layers I was kind of hoping this was three different shades of green green meaning go and red means stop but that that from context-sensitive on down if you can build the language at the context sensitive or using less and less memory its small and smaller we always answer yes oh no but once we get into the languages that are recursively enumerable but the complement of the language is not recursively normal those are languages where we can pants we can always answer yes it really is yes but if the input isn’t no we may go into an infinite