1 00:00:00,000 --> 00:00:04,331 To finish off our discussion of context free languages, let's look at the 2 00:00:04,331 --> 00:00:08,485 properties of this class of languages. Remember, there are two kinds of 3 00:00:08,485 --> 00:00:13,410 properties we find useful. One is decision properties, where we tell something about 4 00:00:13,410 --> 00:00:18,157 a languages or languages in the class. Which is whether the language represented 5 00:00:18,157 --> 00:00:22,666 by a grammar or a PDA is empty. And the other is closure properties, where we 6 00:00:22,666 --> 00:00:27,294 prove that some operation's a union applied to languages in the class, results 7 00:00:27,294 --> 00:00:32,041 in another language in the class. First, let's remember that when we talk about a 8 00:00:32,041 --> 00:00:36,392 decision property, or [inaudible]. Property for a language class we're 9 00:00:36,392 --> 00:00:41,577 talking about algorithms which take a representation for a language class and 10 00:00:41,577 --> 00:00:47,200 produces an answer. For the regular languages, we use regular expressions and 11 00:00:47,200 --> 00:00:52,172 deterministic findings as the representations. Here, for context free 12 00:00:52,172 --> 00:00:57,190 languages, we use the context free grammar, or the push [inaudible] automaton 13 00:00:57,190 --> 00:01:02,275 as the representation, whichever makes like easier. And when we use the PDA, we 14 00:01:02,275 --> 00:01:07,491 can let acceptance be by final state or empty stack. Again, whichever makes life 15 00:01:07,491 --> 00:01:13,865 easiest. Here are some questions about context free languages for which 16 00:01:13,865 --> 00:01:19,468 algorithms exist. Given a representation for a context free language L, and a 17 00:01:19,468 --> 00:01:24,851 string W, we can determine whether or not W is in L. We can tell whether a 18 00:01:24,851 --> 00:01:32,316 representation for context free language L generates the empty language. Then we can 19 00:01:32,316 --> 00:01:38,140 also tell whether this language L is finite or infinite. Unfortunately, many of 20 00:01:38,140 --> 00:01:44,039 the things we can decide about regular languages, we can not decide for context 21 00:01:44,039 --> 00:01:49,528 free languages. For example, we were able to tell whether two regular languages, 22 00:01:49,528 --> 00:01:54,364 say, represented by DFA, were the same. We can't tell whether two context free 23 00:01:54,364 --> 00:01:59,327 grammars or two PDAs define the same language. Another thing we cannot tell is 24 00:01:59,327 --> 00:02:04,418 whether two context free languages are disjoint. We say set to disjoint if their 25 00:02:04,418 --> 00:02:10,159 intersection is empty. That is, they have no members in common. We didn't address 26 00:02:10,159 --> 00:02:14,866 the question of disjointness for regular languages but you can tell whether two 27 00:02:14,866 --> 00:02:19,339 regular languages are disjoint. We showed regular languages are closed under 28 00:02:19,339 --> 00:02:23,987 intersection using the, the product automotron trick. We also showed that you 29 00:02:23,987 --> 00:02:28,224 can tell whether the language of an automotron is empty. These two ideas 30 00:02:28,224 --> 00:02:32,520 together give you an algorithm to test whether two regular languages are 31 00:02:32,520 --> 00:02:38,019 disjoint. At this point we have no way to prove that no algorithm for a task exists. 32 00:02:38,019 --> 00:02:43,056 That is the job of the theory of [inaudible] machines and decidability and 33 00:02:43,056 --> 00:02:48,143 that will be the next big topic that we address. Now the emptiness test for 34 00:02:48,143 --> 00:02:53,181 [inaudible] languages has already been given an essence. We showed how to 35 00:02:53,181 --> 00:02:58,633 eliminate useless symbol. Those that participate in [inaudible] of the terminal 36 00:02:58,633 --> 00:03:04,155 string. Take any context free grammar and see whether or not the start symbol is 37 00:03:04,155 --> 00:03:09,331 useless. If so the language of the grammar is empty. And if not, then not. The 38 00:03:09,331 --> 00:03:15,059 membership test for dfa was really simple. To simulate the dfa on the screen, we can 39 00:03:15,059 --> 00:03:20,403 also test. Whether a terminal string W is generated by a grammar G. But the test is 40 00:03:20,403 --> 00:03:25,187 remarkably hard by comparison. We'll assume G is a grammar and [inaudible] 41 00:03:25,187 --> 00:03:30,099 normal form. If not, we know how to convert the given grammar to CNF, so let's 42 00:03:30,099 --> 00:03:35,335 do that as the first step. There's a small matter that when we convert the CNF, we 43 00:03:35,335 --> 00:03:40,312 lost the ability to generate the empty string. But if W, the string we want to 44 00:03:40,312 --> 00:03:45,419 test, if epsilon, then there is another approach entirely. Apply the algorithm we 45 00:03:45,419 --> 00:03:50,467 learned for finding the knowable symbols. Those that derive epsilon. See if the 46 00:03:50,467 --> 00:03:55,362 start symbol is one of these, and that lets us test membership at the empty 47 00:03:55,362 --> 00:04:00,191 string, in the language of the context free grammar. We're going to give an 48 00:04:00,191 --> 00:04:05,346 algorithm called CYK. The initials stand for the three people who independently 49 00:04:05,346 --> 00:04:10,632 invented the idea. John Cock, Dan Younger, and [inaudible] Kasaki. This algorithm is 50 00:04:10,632 --> 00:04:15,723 a great example of a dynamic programming algorithm, and worth, worth seeing for 51 00:04:15,723 --> 00:04:20,878 that reason alone. The running time of the algorithm is of the order of N cubed, 52 00:04:20,878 --> 00:04:25,957 where N is the length of the input string W. Incidentally, there is another 53 00:04:25,957 --> 00:04:32,139 algorithm due to J Early that also runs in time order n-cubed. But on an unambiguous 54 00:04:32,139 --> 00:04:38,100 grammar Early's Algorithm is faster it's order n-squared. However the CYK is much 55 00:04:38,100 --> 00:04:43,620 simpler and as I said worth studying because it is a model for many useful 56 00:04:43,620 --> 00:04:49,654 dynamic programming algorithms. So that is the one we're going to learn. Here's how 57 00:04:49,654 --> 00:04:55,395 the CYK algorithm works. Start with an input string of length N. Let A sub I be 58 00:04:55,395 --> 00:05:02,252 the symbol in the I-th position. We're going to construct a triangular array with 59 00:05:02,252 --> 00:05:09,420 short sides each of lengths N. Each entry of length is a set of entries in the 60 00:05:09,420 --> 00:05:16,955 grammar. The set X of IJ which will be in position IJ, and I is equal to or less 61 00:05:16,955 --> 00:05:24,122 than J is intended to be the set of variables A that derive the sub string in 62 00:05:24,122 --> 00:05:31,290 the input starting in the position I and ending the position J. That's, that is 63 00:05:31,290 --> 00:05:37,107 this. We'll use an induction to fill the table. The induction is on the length of 64 00:05:37,107 --> 00:05:42,535 the string derived, which is J minus I plus one. So we start by computing the 65 00:05:42,535 --> 00:05:47,964 entries X sub II, which is the set of variables which that derive the string 66 00:05:47,964 --> 00:05:53,678 which is the one position AI. From these we can find the XI, I plus one's each of 67 00:05:53,678 --> 00:05:59,750 which is a set of variable that derive the string AI followed by AI plus one. Then we 68 00:05:59,750 --> 00:06:05,178 move to the XII plus two's which are the sets of variables which derive the 69 00:06:05,178 --> 00:06:12,383 strings. Length three AI, AI plus one AI plus two and so on. Finally, after we have 70 00:06:12,383 --> 00:06:18,574 computed the one set, X1N, which represents the entire input, we can ask 71 00:06:18,574 --> 00:06:25,473 ourselves whether S is in that set. If so then S derives from A1 through N and 72 00:06:25,473 --> 00:06:32,666 string W is in the language and otherwise not. For the basis, we know that The only 73 00:06:32,666 --> 00:06:38,557 way to derive a string of length one in the C and F grammar, is to use a 74 00:06:38,557 --> 00:06:44,694 production whose body is a single terminal. So for each I, we can set XII to 75 00:06:44,694 --> 00:06:51,240 the set of variables A, such that A goes to AI is a production. For the induction. 76 00:06:51,240 --> 00:06:58,148 Where J is strictly greater than I. We can compute x I j from x is representing two 77 00:06:58,148 --> 00:07:05,684 sub-strings of a I through h a. The first is a sub strain from AI to AK for sum K 78 00:07:05,684 --> 00:07:12,420 less than J. And the second is AK+1 through AJ. Both these strings are of 79 00:07:12,420 --> 00:07:20,775 length less than J-I+1. So we have already computed the sets, X of IK. And X sub 80 00:07:20,775 --> 00:07:29,972 K+1J. In order for a variable A to derive AI through AJ there must be some 81 00:07:29,972 --> 00:07:40,786 production. Say A goes to BC. Where B derives AI to AK, and C derives the rest. 82 00:07:40,786 --> 00:07:51,620 That is, for each K between I and J-1, we look for sum B in XIK, and sum C in XK+1J. 83 00:07:53,180 --> 00:07:59,383 Such that BC is the body of an A production. If, for any K, B, and C, we 84 00:07:59,383 --> 00:08:06,681 find such a production, we add A to XIJ. We're going to do an example of the CYKL 85 00:08:06,681 --> 00:08:13,980 algorithm. Here's the CNF grammar we'll use, and the input screen W will be ABABA. 86 00:08:14,620 --> 00:08:21,524 It is a length five so we are going to compute variables XIJ for I less than or 87 00:08:21,524 --> 00:08:28,773 equal to J and I equal to greater than one and J less than or equal to five, that is 88 00:08:28,773 --> 00:08:35,419 a triangular array. For the basis, let's see which variables have a production 89 00:08:35,419 --> 00:08:44,435 who's body is A. These variables are the capital A which has this production and 90 00:08:44,435 --> 00:08:52,754 capital C which has that production. Thus, if W has this symbol, little A in position 91 00:08:52,754 --> 00:09:04,372 I, then XII will be AC. We see A in positions one, three and five of W. That 92 00:09:04,372 --> 00:09:14,865 explains X-1-1, X-3-3 and X-5-5. For terminal b we see body b in productions 93 00:09:14,865 --> 00:09:23,734 for b and c. That's here and here. Thus if I is a position of W that holds B, XII 94 00:09:23,734 --> 00:09:30,626 will be BC. That explains positions two and positions four. Now we need to compute 95 00:09:30,626 --> 00:09:37,809 the four entries in the row above. These are the sets of variables that derive 96 00:09:37,809 --> 00:09:42,737 substrings of length two. Here's one example. X12. Which is the set of 97 00:09:42,737 --> 00:09:48,536 variables which derive the string in the first positions of W, that is AB. When J 98 00:09:48,536 --> 00:09:54,334 is I plus one, K can only be I. That is the only way to derive a string of length 99 00:09:54,334 --> 00:09:59,698 two in a CNF grammar is to use a production where one unit is replaced by 100 00:09:59,698 --> 00:10:09,067 two and each of these variables derives one terminal. So the reason S is in X12 is 101 00:10:09,067 --> 00:10:21,718 that A is in X11, B is in X22, and S goes to AB is a production. And the reason B is 102 00:10:21,718 --> 00:10:31,285 in x1 two is that A is an X11 C is an X22 and B goes to AC as a production. Notice 103 00:10:31,285 --> 00:10:38,392 that C can't be in X12 because C derives only strings of length one. However, A can 104 00:10:38,392 --> 00:10:43,494 derive long strings and yet is not an X-1-2. The reason is that the only 105 00:10:43,494 --> 00:10:51,380 production A has with the body of two variables is A goes to B-C. That's this. 106 00:10:52,500 --> 00:10:59,502 In order for A to be an X-1-2 we would need to find B an X- 1-1 and C an X-2-2. 107 00:10:59,502 --> 00:11:05,885 The latter holds but B is not an X-1-1. Here are the other three sets for the 108 00:11:05,885 --> 00:11:10,812 [inaudible] correspondent to the substrings of length two. We'll leave it 109 00:11:10,812 --> 00:11:16,280 to you to verify that those are correct. Now let's start computing X13. The string 110 00:11:16,280 --> 00:11:21,545 on length three can be broken in two different ways. Either a string of length 111 00:11:21,545 --> 00:11:26,945 one followed by a string of length two, or vice-versa. In the first case, K=1, and we 112 00:11:26,945 --> 00:11:33,990 must combine X11 with X23. X11 has A and C, while X23 has only A. The only bodies 113 00:11:33,990 --> 00:11:41,269 we can form from these are AA and CA. But no variable has a, a production with 114 00:11:41,269 --> 00:11:48,264 either of these as the body. Thus, K=1 gives us nothing. We must also consider 115 00:11:48,264 --> 00:11:55,030 K=2, where we combine X12 with X33. Now, there are four possible bodies, v or s 116 00:11:55,030 --> 00:12:02,244 followed by a or c. Of these, only bc is a body of a production of [inaudible] and 117 00:12:02,244 --> 00:12:10,458 it's head is a. Thus, X-13 turns out to be just the set containing A. Here are the 118 00:12:10,458 --> 00:12:17,305 other two X's with sub-strings of line three. There's a pattern to computing 119 00:12:17,305 --> 00:12:22,981 these corresponding to the choices of K that we may make for each. We start at the 120 00:12:22,981 --> 00:12:32,332 bottom of the column. For example, for X24. That would be X22. We start going 121 00:12:32,332 --> 00:12:40,191 down the diagonal to the right; for X-2-4 that would be X-3-4. So we're going to 122 00:12:40,191 --> 00:12:48,290 pair X-2-2 with X-3-4. We then pair them to see what production bodies we can form. 123 00:12:48,290 --> 00:12:55,183 And then we move up the column. Here, in this case, the x to three, and down the 124 00:12:55,183 --> 00:13:02,437 diagonal, in this case to x. For four. And we pair these two guys to again see what 125 00:13:02,437 --> 00:13:08,457 variables we can form from that one followed by that one. Here's how we 126 00:13:08,457 --> 00:13:15,408 compute x one four. Starting at the bottom of the column that is x one, one. And the 127 00:13:15,408 --> 00:13:23,425 top of it's diagonal that is x two four. We pair these to see if we can form any 128 00:13:23,425 --> 00:13:32,090 production bodies. In this case, we can combine A from X11 and B from X24 to put S 129 00:13:32,090 --> 00:13:41,334 the head of production with body AB into X14. Now we move up the column to X1,2 and 130 00:13:41,334 --> 00:13:49,360 down the diagonal to x3,4. But pairing BRS with BRS doesn't give us any right sides. 131 00:13:49,880 --> 00:13:58,657 So we proceed up the column to X13, and down the diagonal to X14. And we pair A 132 00:13:58,657 --> 00:14:06,950 with B or C. Ac is a body, and it justifies outputting B into X14. Here are 133 00:14:06,950 --> 00:14:14,496 the last two entries in the triangular table. X25 turns out to be the set 134 00:14:14,496 --> 00:14:24,549 containing A we'll let you check that one out and X15 is also A. You get a from x14 135 00:14:24,549 --> 00:14:33,837 which has b and x55 which has c. Bc has a body. And A is it's head. Since S is not 136 00:14:33,837 --> 00:14:38,746 an X15, we can, can conclude that ABABA is not in the language in the given grammar. 137 00:14:38,746 --> 00:14:43,774 We also claim that there is an algorithm to tell whether a context free language is 138 00:14:43,774 --> 00:14:48,503 finite or infinite. We won't give the algorithm in detail but it is essentially 139 00:14:48,503 --> 00:14:53,531 the same as the time algorithm we gave for regular languages. We use the [inaudible] 140 00:14:53,531 --> 00:14:58,020 constant N and as for regular languages, we can show that if a context free 141 00:14:58,020 --> 00:15:02,570 language contains any string of length between N and 2N minus one, then that 142 00:15:02,570 --> 00:15:07,482 string can be pumped and the language in infinite. Otherwise the language Which is 143 00:15:07,482 --> 00:15:12,486 finite. We're now going to enter the area of closure properties. And for many of the 144 00:15:12,486 --> 00:15:17,429 same operations under which the class of regular languages are closed, the context 145 00:15:17,429 --> 00:15:22,191 free languages are also closed. These include the regular expression operations 146 00:15:22,191 --> 00:15:26,652 themselves, union concatenation and closure. And also reversal, homomorphism, 147 00:15:26,652 --> 00:15:31,475 and inverse homomorphism. But unlike the class of regular languages, the class of 148 00:15:31,475 --> 00:15:36,599 context free languages is not closed under intersection or difference. Here's a proof 149 00:15:36,599 --> 00:15:41,199 that the union of two context free languages is a context free language. Let 150 00:15:41,199 --> 00:15:45,871 L and M be the context for languages and let them have grammars G and H, 151 00:15:45,871 --> 00:15:51,256 respectively. We need to rename variables for one of these grammars so no variables 152 00:15:51,256 --> 00:15:56,772 is used for both G and H. The names of the variables don't matter so we can always do 153 00:15:56,772 --> 00:16:02,027 this. The reason it is so important is that we are going to throw the productions 154 00:16:02,027 --> 00:16:07,023 from G and H into one pile and if they had variables in common then we could 155 00:16:07,023 --> 00:16:11,890 accidentally use a production on a variable from H or vice versa. Note that 156 00:16:11,890 --> 00:16:16,870 we do not change the terminals of the grammars It's okay if they terminals in 157 00:16:16,870 --> 00:16:21,852 common in fact, we expect that they will have terminals in common. Suppose S1 and 158 00:16:21,852 --> 00:16:26,709 S2 are the start symbols of the two grammars after renaming the variables. And 159 00:16:26,709 --> 00:16:31,940 we'll build the grammar for L [inaudible] and M by combining all the symbols of the 160 00:16:31,940 --> 00:16:37,170 two grammars G and H. That is the new set of terminals is the union of the terminals 161 00:16:37,170 --> 00:16:42,214 of G and H. And the new set of variables is the union of the variables in G and H 162 00:16:42,214 --> 00:16:47,320 plus a new symbol S which is not a symbol of either grammar and will be the start 163 00:16:47,320 --> 00:16:52,673 symbol of the new grammar. The new set of productions is the union of the 164 00:16:52,673 --> 00:16:58,631 productions of G and H, plus two new productions. S goes to S1, and S goes to 165 00:16:58,631 --> 00:17:05,145 S2. All the derivations of the new grammar start with S. And in the first step, this 166 00:17:05,145 --> 00:17:11,739 S is replaced by either S1 or S2. If S is replaced by S1, then the entire derivation 167 00:17:11,739 --> 00:17:17,855 must be a derivation of G. Because we cannot, then, get any variables of H into 168 00:17:17,855 --> 00:17:23,816 our derivation. Similarly, if the first step gives us [inaudible]. Two, then the 169 00:17:23,816 --> 00:17:29,146 entire derivation is a derivation of H. Thus terminals strings derivable from S 170 00:17:29,146 --> 00:17:34,678 are exactly those in L if we start from S goes to S1. Union those in M if we start 171 00:17:34,678 --> 00:17:40,074 with S goes to S2. That is the grammars new language L union M. The argument that 172 00:17:40,074 --> 00:17:45,404 the class of context free language is disclosed under concatenation starts the 173 00:17:45,404 --> 00:17:50,531 same way with grammars G and H for the languages L and M. These grammars are 174 00:17:50,531 --> 00:17:56,063 assumed to have no variables in common and to have the start symbols be S1 and S2 175 00:17:56,063 --> 00:18:01,075 respectively. Again we combine the two grammars as we did for union. The only 176 00:18:01,075 --> 00:18:06,588 difference is in the production we use for the new start symbol s. Here there's only 177 00:18:06,588 --> 00:18:11,708 one production. S goes to s one followed by s two. That way all strings derived 178 00:18:11,708 --> 00:18:16,959 from s will be a string l followed by a string of m. That is the new [inaudible] 179 00:18:16,959 --> 00:18:22,407 that will generate l concatenated with m. The [inaudible] star. Let's start with the 180 00:18:22,407 --> 00:18:27,658 grammar g for the language l. Let this grammar have a start symbol as one. Form a 181 00:18:27,658 --> 00:18:33,483 new grammar, by adding the g, a new start symbol as. And the productions S goes to 182 00:18:33,483 --> 00:18:40,436 S1S or the empty string. In a [inaudible] derivation from S, begins from generating 183 00:18:40,436 --> 00:18:46,795 zero or more S1s. That is it uses this production as many times as it likes 184 00:18:46,795 --> 00:18:53,663 followed by S goes to Epsilon. From each of these S1s we can generate exactly the 185 00:18:53,663 --> 00:18:59,683 strings and Ls so the new grammar generates L star. Reversal is another 186 00:18:59,683 --> 00:19:05,813 operation for which it is easy to show closure using grammars. If we have a 187 00:19:05,813 --> 00:19:11,054 grammar G for the language L, we form a grammar for L reverse by reversing the 188 00:19:11,054 --> 00:19:15,959 bodies of all the productions of G. For example, here is a grammar for the 189 00:19:15,959 --> 00:19:20,864 language zero to the N, one to the N. If we reverse the bodies, we get this 190 00:19:20,864 --> 00:19:25,971 grammar. It is easy to see that this grammar generates all strings of one or 191 00:19:25,971 --> 00:19:31,414 more 1s followed by the same number of zeros. That language is the reverse of the 192 00:19:31,414 --> 00:19:36,856 language we started with. We're not going to give up proof that this construction 193 00:19:36,856 --> 00:19:41,743 works. It is a simple induction The lengths of derivations and the two 194 00:19:41,743 --> 00:19:47,565 parameters. To prove closure of this and the context free value language which is 195 00:19:47,565 --> 00:19:53,603 under homomorphism, so let's start with a parameter G for a language L and let H be 196 00:19:53,603 --> 00:19:59,354 the homomorphism of the terminal symbols of G. And H has a grammar which we can 197 00:19:59,354 --> 00:20:05,176 construct by replacing each terminal A in the body of any production of G by the 198 00:20:05,176 --> 00:20:10,855 string H of A. So for example here is, G is our customary grammar for G to the N 199 00:20:10,855 --> 00:20:16,219 one to the N. And here is our. Usual example of the homomorphism. Then h 200 00:20:16,219 --> 00:20:21,774 applied to the language of g has a grammar in which the two occurrences of zero in 201 00:20:21,774 --> 00:20:26,861 the productions of g are replaces by a b. And the two occurrences of one are 202 00:20:26,861 --> 00:20:32,349 replaced by the empty string Notice that the resulting language is all strings of 203 00:20:32,349 --> 00:20:37,904 one or more a b. It is in fact the regular language. Although in general, we can only 204 00:20:37,904 --> 00:20:43,125 be sure that it will be a context free language. Next, we take up the fact that 205 00:20:43,125 --> 00:20:48,159 context free languages are close to inversal [inaudible]. Well, we seem to 206 00:20:48,159 --> 00:20:54,334 have done pretty well using a [inaudible] representation for context [inaudible] 207 00:20:54,334 --> 00:21:00,357 languages so far. Here we really need the pda representation. Start with a pda p 208 00:21:00,357 --> 00:21:06,379 that accepts the language l by final state. We'll construct another pda p prime 209 00:21:06,379 --> 00:21:12,478 which accepts h inverse of l. Where h is [inaudible]. The big idea is the p prime 210 00:21:12,478 --> 00:21:17,661 will simulate p. But p prime needs to apply h to every input in both 211 00:21:17,661 --> 00:21:22,992 [inaudible]. And since h of A may be a long. String P prime has trouble 212 00:21:22,992 --> 00:21:28,998 simulating P in one move and often it cannot do so, so P prime will take it one 213 00:21:28,998 --> 00:21:34,843 step at a time. It has a state with two components, the first. Is the state of P 214 00:21:34,843 --> 00:21:40,474 which is important in the simulation. But the second is a buffer that holds the 215 00:21:40,474 --> 00:21:46,033 suffix of what you get by applying H to someone's symbol. This buffer allows P 216 00:21:46,033 --> 00:21:51,450 prime to use the symbols of H of A, one symbol at a time, to cause moves of P. 217 00:21:51,450 --> 00:21:56,868 Here's a rough sketch of what P prime looks like. As mentioned, its state has 218 00:21:56,868 --> 00:22:02,427 two components, the state of P and the buffer. We show input 0011 as an example 219 00:22:02,427 --> 00:22:07,814 only. Now, P prime can read its first input symbol zero, and apply H to it. The 220 00:22:07,814 --> 00:22:12,844 buffer which was initially empty now has the string H of zero. It may be a long 221 00:22:12,844 --> 00:22:17,747 string but it's length is finite so there's only a finite number of states P 222 00:22:17,747 --> 00:22:22,840 prime could be in. Now to simulate P, P prime takes the first symbol of H of zero 223 00:22:22,840 --> 00:22:27,998 and simulates P using that as the next input symbol. The simulation can take many 224 00:22:27,998 --> 00:22:33,028 moves as they can be transitions on epsilon input as well as one transition on 225 00:22:33,028 --> 00:22:38,121 the symbol itself. However the symbol is removed from the front of the buffer so 226 00:22:38,121 --> 00:22:43,689 the next time P needs a real input symbol, it gets the [inaudible] Of H of zero. The 227 00:22:43,689 --> 00:22:49,711 simulation proceeds in this manner. Until all symbols of h of zero aren't consumed 228 00:22:49,711 --> 00:22:55,512 from the buffer. At that point, p prime can apply h to its next input. And refill 229 00:22:55,512 --> 00:23:01,387 the [inaudible], the buffer. To be more precise, the states of p prime are pairs q 230 00:23:01,387 --> 00:23:07,261 w where q is the state of p. And w is a suffix of h and A, for some symbol A. Note 231 00:23:07,261 --> 00:23:13,503 that given p and h there are only a finite number of values of w. And of course p has 232 00:23:13,503 --> 00:23:19,486 a finite number of states q. So P prime also has a finite number of states, as is 233 00:23:19,486 --> 00:23:25,526 required for any PDA. The stack symbols of P prime are those of P. Moreover, as we 234 00:23:25,526 --> 00:23:31,717 shall see, the stack behavior of P Prime mimics that of P. And the start state of P 235 00:23:31,717 --> 00:23:37,622 Prime. Q zero epsilon. That is the stars theta of P, paired with an empty buffer. 236 00:23:37,622 --> 00:23:43,755 The input symbols of P prime are those symbols A for which H of A is defined. And 237 00:23:43,755 --> 00:23:50,040 the final states of P prime are the final states P paired with an empty buffer. Now 238 00:23:50,040 --> 00:23:56,174 we'll show how P prime simulates P by giving the transition function delta-prime 239 00:23:56,174 --> 00:24:02,383 for P prime. The first type of transition allows P prime to read an input symbol A 240 00:24:02,383 --> 00:24:08,520 which must not be epsilon. Apply H to it and store. In the buffer. The buffer of P 241 00:24:08,520 --> 00:24:14,630 prime must be empty for this to happen. Although, since P might be able to make 242 00:24:14,630 --> 00:24:21,054 moves with epsilon input, P prime is no reforced to refill the buffer just because 243 00:24:21,054 --> 00:24:27,087 it is empty. If can also makes moves without consuming its own input. Formally, 244 00:24:27,087 --> 00:24:33,354 delta prime of Q epsilon A and X, that's this, has one choice. It can remove the A 245 00:24:33,354 --> 00:24:39,464 from its input. And you remember, A is not empty. Place H of A in the buffer, and 246 00:24:39,464 --> 00:24:46,071 leave it. Stack and state unchanged. Note that H of A might be empty, in which case, 247 00:24:46,071 --> 00:24:52,793 the buffer remains empty. But it is also possible that the buffer now contains one 248 00:24:52,793 --> 00:24:59,760 or more of P's input symbols. P prime also has the option to ignore its own input and 249 00:24:59,760 --> 00:25:06,832 simulate P as if P's input or whatever it is in the buffer. Formally, suppose. That 250 00:25:06,832 --> 00:25:17,758 delta of. Q, B and X. Contains P alpha. Here P may be epsilon or it may be an 251 00:25:17,758 --> 00:25:25,973 input symbol of P. And then for any buffer string of the form BW, that is a suffix of 252 00:25:25,973 --> 00:25:33,797 H of A for some A, delta prime of Q and the buffer BW with no input with epsilon 253 00:25:33,797 --> 00:25:41,159 input and X on the top of the stack will contain. Pw alpha. That is, B is consumed 254 00:25:41,159 --> 00:25:48,203 from the front of the buffer. The state of P changes according to the given choice of 255 00:25:48,203 --> 00:25:54,585 P's move. And the stack of P prime also changes in accordance with that given 256 00:25:54,585 --> 00:26:00,213 move. In order to prove that P prime does what we want it to do, that is, accept H 257 00:26:00,213 --> 00:26:05,496 inverse of the language PDAP, we need to do two inductive proofs, one in each 258 00:26:05,496 --> 00:26:10,432 direction of the statement that characterizes the way in which P prime 259 00:26:10,432 --> 00:26:15,715 simulates P. We're not gonna give the proofs here. The precise statement of P 260 00:26:15,715 --> 00:26:21,346 prime stimulates P is given in the middle of the slide. It says that P prime goes 261 00:26:21,346 --> 00:26:30,402 from its initial ID with input X. That's this. To some id with state q of p, buffer 262 00:26:30,402 --> 00:26:39,349 contents x, w consumed from the input and alpha on its stack, and that's this. If 263 00:26:39,349 --> 00:26:50,743 and only if, well, first of all. P goes from its initial ID with input Y. That, to 264 00:26:50,743 --> 00:26:59,604 an id that state q, input y consumed, and alpha on its' stat. That's that. And 265 00:26:59,604 --> 00:27:06,920 second, H of W is Y. That's what? P consumed. Followed by X, which is the 266 00:27:06,920 --> 00:27:14,243 thing that P prime still has left in its buffer. Once we have that, we can restrict 267 00:27:14,243 --> 00:27:19,631 it to this case where X is empty, and Q is a final state. It then says that P prime 268 00:27:19,631 --> 00:27:24,821 accepts W if and only if P accepts H of W. That is the language of P prime is H 269 00:27:24,821 --> 00:27:30,208 inverse of the language of P. We have not yet addressed intersection. Remember that 270 00:27:30,208 --> 00:27:34,873 the regular languages are closed under intersection, and then we proved 271 00:27:34,873 --> 00:27:39,877 [inaudible] running DFAs for the two languages in parallel. But we can't run 272 00:27:39,877 --> 00:27:45,447 two PDAs in parallel and still have a PDA. The reason is that the parallel execution 273 00:27:45,447 --> 00:27:50,155 of two PDAs requires two separate independent stacks and a PDA is only 274 00:27:50,155 --> 00:27:55,226 allowed to have one stack. That's only an argument that the obvious first try 275 00:27:55,226 --> 00:27:59,794 approving context-free languages are closed under intersection won't work, but 276 00:27:59,794 --> 00:28:03,776 the situation is worse. We can see particular context-free languages 277 00:28:03,776 --> 00:28:08,051 [inaudible] intersection was not a context-free language so no construct 278 00:28:08,051 --> 00:28:13,191 could possibly. We said that this language L1, the set of strings of some number zero 279 00:28:13,191 --> 00:28:18,007 is followed with the same number of ones and the same number of twos, is not a 280 00:28:18,007 --> 00:28:22,948 context free language. The [inaudible] gives us an easy proof of that fact. We're 281 00:28:22,948 --> 00:28:28,444 not going to do it here but it's very much like the example [inaudible] proof that we 282 00:28:28,444 --> 00:28:34,880 did give. But consider L2 the set of strings in zero star one star two star. 283 00:28:34,880 --> 00:28:41,041 That is, strings of zeros followed by some number of ones, followed by some number of 284 00:28:41,041 --> 00:28:46,982 twos. Such that the number of zeros and ones are the same with any number of twos. 285 00:28:46,982 --> 00:28:52,630 This language is context free, and here is a little grammar for it. The job of 286 00:28:52,630 --> 00:28:58,645 variable A is to generate, zeros followed by an equal number of ones. We've seen 287 00:28:58,645 --> 00:29:04,439 this mechanism several times before. And B generates just any number of twos, at 288 00:29:04,439 --> 00:29:11,400 least one of them. Now let L3 be the set of strings in zero star one star two star. 289 00:29:11,820 --> 00:29:17,016 Equal numbers of ones and twos, and with any number of zeros. This language is also 290 00:29:17,016 --> 00:29:22,022 context free, and the grammar for L3 uses the same ideas as the grammar we just 291 00:29:22,022 --> 00:29:27,092 showed for L2. But L1 is the intersection of context-free languages L2 and L3. We 292 00:29:27,092 --> 00:29:32,352 can also show that the difference of two context free languages is not necessarily 293 00:29:32,352 --> 00:29:37,104 context free. In fact we can prove something surprising. Intersection can be 294 00:29:37,104 --> 00:29:42,237 expressed in terms of difference alone. Therefore any class of language is closed 295 00:29:42,237 --> 00:29:48,981 under difference, it is also closed under intersection. The argument is that any, 296 00:29:48,981 --> 00:29:54,881 the intersection of any two languages L and M, regardless of whether they're 297 00:29:54,881 --> 00:30:02,084 regular context free or not context free, is the difference between L and L-M. That 298 00:30:02,084 --> 00:30:13,588 is, suppose X is into L too second M. Okay, than X is surely. Not in L minus M, 299 00:30:13,588 --> 00:30:21,246 because it's in both L and M. And therefore, X is in L, and not in L minus 300 00:30:21,246 --> 00:30:30,749 M. Therefore, it is in this expression on the, on the right side. That proves 301 00:30:30,749 --> 00:30:38,930 containment in one direction. For the other direction, suppose X is in L-L-M, 302 00:30:38,930 --> 00:30:48,001 that's this guy here. Then X is in L, and it's not in L-M. But if x is in l but not 303 00:30:48,001 --> 00:30:57,267 in l minus m, it must be, that x is also in m. Thus, X is in. L intersect M. That 304 00:30:57,267 --> 00:31:02,865 proves containment in the other direction that is X here implied X there and that 305 00:31:02,865 --> 00:31:07,849 proves the equivalence of these two expressions. Now suppose the class of 306 00:31:07,849 --> 00:31:13,379 context free languages were closed under difference and L and M are context free 307 00:31:13,379 --> 00:31:18,773 languages. Then L minus M would be context free and so would this guy, L minus L 308 00:31:18,773 --> 00:31:24,030 minus M. But we just proved that this expression is the same as L intersect M, 309 00:31:24,030 --> 00:31:29,150 thus context free languages would be closed under intersection but we know 310 00:31:29,150 --> 00:31:34,751 they're not So we know that they cannot be closed under intersection but we know 311 00:31:34,751 --> 00:31:40,196 they're not so we know that they cannot be closed under difference either. We know 312 00:31:40,196 --> 00:31:45,376 that the intersection of two context free languages may not be a context free 313 00:31:45,376 --> 00:31:50,024 language. However if we intersect a context free language in a regular 314 00:31:50,024 --> 00:31:55,337 language then we always get a context free language. The idea is to run a DFA in 315 00:31:55,337 --> 00:32:00,516 parallel with a PDA, since the DFA has not stack, we do not face the problem of 316 00:32:00,516 --> 00:32:05,681 trying to simulate two stacks with one that we face Try to run two PDAs in 317 00:32:05,681 --> 00:32:11,781 parallel. Here's the picture of a PDA and DFA running in parallel. We could combine 318 00:32:11,781 --> 00:32:17,733 the states of the two automata to make one state for new PDA, it manipulates the 319 00:32:17,733 --> 00:32:24,057 stack of the original PDA and feeds inputs into both the original PDA and the DFA. It 320 00:32:24,057 --> 00:32:30,232 accepts if both the PDA and DFA accept. To give the construction of the new PDA let 321 00:32:30,232 --> 00:32:35,886 the DFA have a transition function delta A and the original PDA will have a 322 00:32:35,886 --> 00:32:42,032 transition function delta P. States of the new PDA will be pairs. The first 323 00:32:42,032 --> 00:32:49,362 component, Q is a state of the DFA and the second component, P is a state of the PDA. 324 00:32:49,362 --> 00:32:56,692 Suppose the original PDA has a choice of move from state P in stack symbol X, where 325 00:32:56,692 --> 00:33:03,933 A is consumed from the input. That's this. A could be a real symbol or absolute. The 326 00:33:03,933 --> 00:33:11,175 result of the move is that the PDA state becomes R and X on the stack is replaced 327 00:33:11,175 --> 00:33:18,526 by Alpha. That's the move. Then they [inaudible] PVA who's transition function 328 00:33:18,526 --> 00:33:26,143 we call simply delta. Given a state where P is the second component input A and 329 00:33:26,143 --> 00:33:33,181 stack symbol X that's this. Has a [inaudible] of move where the new state 330 00:33:33,181 --> 00:33:40,042 has second component R. The first component is what you get. By having the 331 00:33:40,042 --> 00:33:46,489 dfa make a transition from state q with input A. That's delta A of q and A. It 332 00:33:46,489 --> 00:33:53,187 could be [inaudible] here in which case delta A of q A is just q. Or it could be 333 00:33:53,187 --> 00:33:59,634 real simple in which delta A of q A is something else. Finally this choice of 334 00:33:59,634 --> 00:34:06,080 move replaces x by alpha on the stack. Just as the original pda did. The final 335 00:34:06,080 --> 00:34:11,698 stage of the new pda is the [inaudible]. Such that Q and P are final states of 336 00:34:11,698 --> 00:34:16,896 their respective [inaudible]. And the initial state of the new PDA is the pair 337 00:34:16,896 --> 00:34:22,627 consisting of the initial states of both [inaudible]. We need to prove a pair of 338 00:34:22,627 --> 00:34:28,358 inductions on the number of moves made by each PDA. These inductions say that the 339 00:34:28,358 --> 00:34:34,678 new PDA started in its initial state with input W, this. Consumes the input, and 340 00:34:34,678 --> 00:34:42,492 enters an ID with state QP. Okay, and stack alpha having consumed the input. 341 00:34:42,492 --> 00:34:56,079 Okay, and that happens if and only if. The original PDA goes from its initial ID with 342 00:34:56,079 --> 00:35:07,738 input W. To the ID with the same state P, and alpha on the stack. And of course the 343 00:35:07,738 --> 00:35:17,295 DFA. Goes from it's initial state on input W to the state Q. Skip the details as the 344 00:35:17,295 --> 00:35:19,840 proofs are not too hard.