To finish off our discussion of context free languages, let's look at the
properties of this class of languages. Remember, there are two kinds of
properties we find useful. One is decision properties, where we tell something about
a languages or languages in the class. Which is whether the language represented
by a grammar or a PDA is empty. And the other is closure properties, where we
prove that some operation's a union applied to languages in the class, results
in another language in the class. First, let's remember that when we talk about a
decision property, or [inaudible]. Property for a language class we're
talking about algorithms which take a representation for a language class and
produces an answer. For the regular languages, we use regular expressions and
deterministic findings as the representations. Here, for context free
languages, we use the context free grammar, or the push [inaudible] automaton
as the representation, whichever makes like easier. And when we use the PDA, we
can let acceptance be by final state or empty stack. Again, whichever makes life
easiest. Here are some questions about context free languages for which
algorithms exist. Given a representation for a context free language L, and a
string W, we can determine whether or not W is in L. We can tell whether a
representation for context free language L generates the empty language. Then we can
also tell whether this language L is finite or infinite. Unfortunately, many of
the things we can decide about regular languages, we can not decide for context
free languages. For example, we were able to tell whether two regular languages,
say, represented by DFA, were the same. We can't tell whether two context free
grammars or two PDAs define the same language. Another thing we cannot tell is
whether two context free languages are disjoint. We say set to disjoint if their
intersection is empty. That is, they have no members in common. We didn't address
the question of disjointness for regular languages but you can tell whether two
regular languages are disjoint. We showed regular languages are closed under
intersection using the, the product automotron trick. We also showed that you
can tell whether the language of an automotron is empty. These two ideas
together give you an algorithm to test whether two regular languages are
disjoint. At this point we have no way to prove that no algorithm for a task exists.
That is the job of the theory of [inaudible] machines and decidability and
that will be the next big topic that we address. Now the emptiness test for
[inaudible] languages has already been given an essence. We showed how to
eliminate useless symbol. Those that participate in [inaudible] of the terminal
string. Take any context free grammar and see whether or not the start symbol is
useless. If so the language of the grammar is empty. And if not, then not. The
membership test for dfa was really simple. To simulate the dfa on the screen, we can
also test. Whether a terminal string W is generated by a grammar G. But the test is
remarkably hard by comparison. We'll assume G is a grammar and [inaudible]
normal form. If not, we know how to convert the given grammar to CNF, so let's
do that as the first step. There's a small matter that when we convert the CNF, we
lost the ability to generate the empty string. But if W, the string we want to
test, if epsilon, then there is another approach entirely. Apply the algorithm we
learned for finding the knowable symbols. Those that derive epsilon. See if the
start symbol is one of these, and that lets us test membership at the empty
string, in the language of the context free grammar. We're going to give an
algorithm called CYK. The initials stand for the three people who independently
invented the idea. John Cock, Dan Younger, and [inaudible] Kasaki. This algorithm is
a great example of a dynamic programming algorithm, and worth, worth seeing for
that reason alone. The running time of the algorithm is of the order of N cubed,
where N is the length of the input string W. Incidentally, there is another
algorithm due to J Early that also runs in time order n-cubed. But on an unambiguous
grammar Early's Algorithm is faster it's order n-squared. However the CYK is much
simpler and as I said worth studying because it is a model for many useful
dynamic programming algorithms. So that is the one we're going to learn. Here's how
the CYK algorithm works. Start with an input string of length N. Let A sub I be
the symbol in the I-th position. We're going to construct a triangular array with
short sides each of lengths N. Each entry of length is a set of entries in the
grammar. The set X of IJ which will be in position IJ, and I is equal to or less
than J is intended to be the set of variables A that derive the sub string in
the input starting in the position I and ending the position J. That's, that is
this. We'll use an induction to fill the table. The induction is on the length of
the string derived, which is J minus I plus one. So we start by computing the
entries X sub II, which is the set of variables which that derive the string
which is the one position AI. From these we can find the XI, I plus one's each of
which is a set of variable that derive the string AI followed by AI plus one. Then we
move to the XII plus two's which are the sets of variables which derive the
strings. Length three AI, AI plus one AI plus two and so on. Finally, after we have
computed the one set, X1N, which represents the entire input, we can ask
ourselves whether S is in that set. If so then S derives from A1 through N and
string W is in the language and otherwise not. For the basis, we know that The only
way to derive a string of length one in the C and F grammar, is to use a
production whose body is a single terminal. So for each I, we can set XII to
the set of variables A, such that A goes to AI is a production. For the induction.
Where J is strictly greater than I. We can compute x I j from x is representing two
sub-strings of a I through h a. The first is a sub strain from AI to AK for sum K
less than J. And the second is AK+1 through AJ. Both these strings are of
length less than J-I+1. So we have already computed the sets, X of IK. And X sub
K+1J. In order for a variable A to derive AI through AJ there must be some
production. Say A goes to BC. Where B derives AI to AK, and C derives the rest.
That is, for each K between I and J-1, we look for sum B in XIK, and sum C in XK+1J.
Such that BC is the body of an A production. If, for any K, B, and C, we
find such a production, we add A to XIJ. We're going to do an example of the CYKL
algorithm. Here's the CNF grammar we'll use, and the input screen W will be ABABA.
It is a length five so we are going to compute variables XIJ for I less than or
equal to J and I equal to greater than one and J less than or equal to five, that is
a triangular array. For the basis, let's see which variables have a production
who's body is A. These variables are the capital A which has this production and
capital C which has that production. Thus, if W has this symbol, little A in position
I, then XII will be AC. We see A in positions one, three and five of W. That
explains X-1-1, X-3-3 and X-5-5. For terminal b we see body b in productions
for b and c. That's here and here. Thus if I is a position of W that holds B, XII
will be BC. That explains positions two and positions four. Now we need to compute
the four entries in the row above. These are the sets of variables that derive
substrings of length two. Here's one example. X12. Which is the set of
variables which derive the string in the first positions of W, that is AB. When J
is I plus one, K can only be I. That is the only way to derive a string of length
two in a CNF grammar is to use a production where one unit is replaced by
two and each of these variables derives one terminal. So the reason S is in X12 is
that A is in X11, B is in X22, and S goes to AB is a production. And the reason B is
in x1 two is that A is an X11 C is an X22 and B goes to AC as a production. Notice
that C can't be in X12 because C derives only strings of length one. However, A can
derive long strings and yet is not an X-1-2. The reason is that the only
production A has with the body of two variables is A goes to B-C. That's this.
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.
The latter holds but B is not an X-1-1. Here are the other three sets for the
[inaudible] correspondent to the substrings of length two. We'll leave it
to you to verify that those are correct. Now let's start computing X13. The string
on length three can be broken in two different ways. Either a string of length
one followed by a string of length two, or vice-versa. In the first case, K=1, and we
must combine X11 with X23. X11 has A and C, while X23 has only A. The only bodies
we can form from these are AA and CA. But no variable has a, a production with
either of these as the body. Thus, K=1 gives us nothing. We must also consider
K=2, where we combine X12 with X33. Now, there are four possible bodies, v or s
followed by a or c. Of these, only bc is a body of a production of [inaudible] and
it's head is a. Thus, X-13 turns out to be just the set containing A. Here are the
other two X's with sub-strings of line three. There's a pattern to computing
these corresponding to the choices of K that we may make for each. We start at the
bottom of the column. For example, for X24. That would be X22. We start going
down the diagonal to the right; for X-2-4 that would be X-3-4. So we're going to
pair X-2-2 with X-3-4. We then pair them to see what production bodies we can form.
And then we move up the column. Here, in this case, the x to three, and down the
diagonal, in this case to x. For four. And we pair these two guys to again see what
variables we can form from that one followed by that one. Here's how we
compute x one four. Starting at the bottom of the column that is x one, one. And the
top of it's diagonal that is x two four. We pair these to see if we can form any
production bodies. In this case, we can combine A from X11 and B from X24 to put S
the head of production with body AB into X14. Now we move up the column to X1,2 and
down the diagonal to x3,4. But pairing BRS with BRS doesn't give us any right sides.
So we proceed up the column to X13, and down the diagonal to X14. And we pair A
with B or C. Ac is a body, and it justifies outputting B into X14. Here are
the last two entries in the triangular table. X25 turns out to be the set
containing A we'll let you check that one out and X15 is also A. You get a from x14
which has b and x55 which has c. Bc has a body. And A is it's head. Since S is not
an X15, we can, can conclude that ABABA is not in the language in the given grammar.
We also claim that there is an algorithm to tell whether a context free language is
finite or infinite. We won't give the algorithm in detail but it is essentially
the same as the time algorithm we gave for regular languages. We use the [inaudible]
constant N and as for regular languages, we can show that if a context free
language contains any string of length between N and 2N minus one, then that
string can be pumped and the language in infinite. Otherwise the language Which is
finite. We're now going to enter the area of closure properties. And for many of the
same operations under which the class of regular languages are closed, the context
free languages are also closed. These include the regular expression operations
themselves, union concatenation and closure. And also reversal, homomorphism,
and inverse homomorphism. But unlike the class of regular languages, the class of
context free languages is not closed under intersection or difference. Here's a proof
that the union of two context free languages is a context free language. Let
L and M be the context for languages and let them have grammars G and H,
respectively. We need to rename variables for one of these grammars so no variables
is used for both G and H. The names of the variables don't matter so we can always do
this. The reason it is so important is that we are going to throw the productions
from G and H into one pile and if they had variables in common then we could
accidentally use a production on a variable from H or vice versa. Note that
we do not change the terminals of the grammars It's okay if they terminals in
common in fact, we expect that they will have terminals in common. Suppose S1 and
S2 are the start symbols of the two grammars after renaming the variables. And
we'll build the grammar for L [inaudible] and M by combining all the symbols of the
two grammars G and H. That is the new set of terminals is the union of the terminals
of G and H. And the new set of variables is the union of the variables in G and H
plus a new symbol S which is not a symbol of either grammar and will be the start
symbol of the new grammar. The new set of productions is the union of the
productions of G and H, plus two new productions. S goes to S1, and S goes to
S2. All the derivations of the new grammar start with S. And in the first step, this
S is replaced by either S1 or S2. If S is replaced by S1, then the entire derivation
must be a derivation of G. Because we cannot, then, get any variables of H into
our derivation. Similarly, if the first step gives us [inaudible]. Two, then the
entire derivation is a derivation of H. Thus terminals strings derivable from S
are exactly those in L if we start from S goes to S1. Union those in M if we start
with S goes to S2. That is the grammars new language L union M. The argument that
the class of context free language is disclosed under concatenation starts the
same way with grammars G and H for the languages L and M. These grammars are
assumed to have no variables in common and to have the start symbols be S1 and S2
respectively. Again we combine the two grammars as we did for union. The only
difference is in the production we use for the new start symbol s. Here there's only
one production. S goes to s one followed by s two. That way all strings derived
from s will be a string l followed by a string of m. That is the new [inaudible]
that will generate l concatenated with m. The [inaudible] star. Let's start with the
grammar g for the language l. Let this grammar have a start symbol as one. Form a
new grammar, by adding the g, a new start symbol as. And the productions S goes to
S1S or the empty string. In a [inaudible] derivation from S, begins from generating
zero or more S1s. That is it uses this production as many times as it likes
followed by S goes to Epsilon. From each of these S1s we can generate exactly the
strings and Ls so the new grammar generates L star. Reversal is another
operation for which it is easy to show closure using grammars. If we have a
grammar G for the language L, we form a grammar for L reverse by reversing the
bodies of all the productions of G. For example, here is a grammar for the
language zero to the N, one to the N. If we reverse the bodies, we get this
grammar. It is easy to see that this grammar generates all strings of one or
more 1s followed by the same number of zeros. That language is the reverse of the
language we started with. We're not going to give up proof that this construction
works. It is a simple induction The lengths of derivations and the two
parameters. To prove closure of this and the context free value language which is
under homomorphism, so let's start with a parameter G for a language L and let H be
the homomorphism of the terminal symbols of G. And H has a grammar which we can
construct by replacing each terminal A in the body of any production of G by the
string H of A. So for example here is, G is our customary grammar for G to the N
one to the N. And here is our. Usual example of the homomorphism. Then h
applied to the language of g has a grammar in which the two occurrences of zero in
the productions of g are replaces by a b. And the two occurrences of one are
replaced by the empty string Notice that the resulting language is all strings of
one or more a b. It is in fact the regular language. Although in general, we can only
be sure that it will be a context free language. Next, we take up the fact that
context free languages are close to inversal [inaudible]. Well, we seem to
have done pretty well using a [inaudible] representation for context [inaudible]
languages so far. Here we really need the pda representation. Start with a pda p
that accepts the language l by final state. We'll construct another pda p prime
which accepts h inverse of l. Where h is [inaudible]. The big idea is the p prime
will simulate p. But p prime needs to apply h to every input in both
[inaudible]. And since h of A may be a long. String P prime has trouble
simulating P in one move and often it cannot do so, so P prime will take it one
step at a time. It has a state with two components, the first. Is the state of P
which is important in the simulation. But the second is a buffer that holds the
suffix of what you get by applying H to someone's symbol. This buffer allows P
prime to use the symbols of H of A, one symbol at a time, to cause moves of P.
Here's a rough sketch of what P prime looks like. As mentioned, its state has
two components, the state of P and the buffer. We show input 0011 as an example
only. Now, P prime can read its first input symbol zero, and apply H to it. The
buffer which was initially empty now has the string H of zero. It may be a long
string but it's length is finite so there's only a finite number of states P
prime could be in. Now to simulate P, P prime takes the first symbol of H of zero
and simulates P using that as the next input symbol. The simulation can take many
moves as they can be transitions on epsilon input as well as one transition on
the symbol itself. However the symbol is removed from the front of the buffer so
the next time P needs a real input symbol, it gets the [inaudible] Of H of zero. The
simulation proceeds in this manner. Until all symbols of h of zero aren't consumed
from the buffer. At that point, p prime can apply h to its next input. And refill
the [inaudible], the buffer. To be more precise, the states of p prime are pairs q
w where q is the state of p. And w is a suffix of h and A, for some symbol A. Note
that given p and h there are only a finite number of values of w. And of course p has
a finite number of states q. So P prime also has a finite number of states, as is
required for any PDA. The stack symbols of P prime are those of P. Moreover, as we
shall see, the stack behavior of P Prime mimics that of P. And the start state of P
Prime. Q zero epsilon. That is the stars theta of P, paired with an empty buffer.
The input symbols of P prime are those symbols A for which H of A is defined. And
the final states of P prime are the final states P paired with an empty buffer. Now
we'll show how P prime simulates P by giving the transition function delta-prime
for P prime. The first type of transition allows P prime to read an input symbol A
which must not be epsilon. Apply H to it and store. In the buffer. The buffer of P
prime must be empty for this to happen. Although, since P might be able to make
moves with epsilon input, P prime is no reforced to refill the buffer just because
it is empty. If can also makes moves without consuming its own input. Formally,
delta prime of Q epsilon A and X, that's this, has one choice. It can remove the A
from its input. And you remember, A is not empty. Place H of A in the buffer, and
leave it. Stack and state unchanged. Note that H of A might be empty, in which case,
the buffer remains empty. But it is also possible that the buffer now contains one
or more of P's input symbols. P prime also has the option to ignore its own input and
simulate P as if P's input or whatever it is in the buffer. Formally, suppose. That
delta of. Q, B and X. Contains P alpha. Here P may be epsilon or it may be an
input symbol of P. And then for any buffer string of the form BW, that is a suffix of
H of A for some A, delta prime of Q and the buffer BW with no input with epsilon
input and X on the top of the stack will contain. Pw alpha. That is, B is consumed
from the front of the buffer. The state of P changes according to the given choice of
P's move. And the stack of P prime also changes in accordance with that given
move. In order to prove that P prime does what we want it to do, that is, accept H
inverse of the language PDAP, we need to do two inductive proofs, one in each
direction of the statement that characterizes the way in which P prime
simulates P. We're not gonna give the proofs here. The precise statement of P
prime stimulates P is given in the middle of the slide. It says that P prime goes
from its initial ID with input X. That's this. To some id with state q of p, buffer
contents x, w consumed from the input and alpha on its stack, and that's this. If
and only if, well, first of all. P goes from its initial ID with input Y. That, to
an id that state q, input y consumed, and alpha on its' stat. That's that. And
second, H of W is Y. That's what? P consumed. Followed by X, which is the
thing that P prime still has left in its buffer. Once we have that, we can restrict
it to this case where X is empty, and Q is a final state. It then says that P prime
accepts W if and only if P accepts H of W. That is the language of P prime is H
inverse of the language of P. We have not yet addressed intersection. Remember that
the regular languages are closed under intersection, and then we proved
[inaudible] running DFAs for the two languages in parallel. But we can't run
two PDAs in parallel and still have a PDA. The reason is that the parallel execution
of two PDAs requires two separate independent stacks and a PDA is only
allowed to have one stack. That's only an argument that the obvious first try
approving context-free languages are closed under intersection won't work, but
the situation is worse. We can see particular context-free languages
[inaudible] intersection was not a context-free language so no construct
could possibly. We said that this language L1, the set of strings of some number zero
is followed with the same number of ones and the same number of twos, is not a
context free language. The [inaudible] gives us an easy proof of that fact. We're
not going to do it here but it's very much like the example [inaudible] proof that we
did give. But consider L2 the set of strings in zero star one star two star.
That is, strings of zeros followed by some number of ones, followed by some number of
twos. Such that the number of zeros and ones are the same with any number of twos.
This language is context free, and here is a little grammar for it. The job of
variable A is to generate, zeros followed by an equal number of ones. We've seen
this mechanism several times before. And B generates just any number of twos, at
least one of them. Now let L3 be the set of strings in zero star one star two star.
Equal numbers of ones and twos, and with any number of zeros. This language is also
context free, and the grammar for L3 uses the same ideas as the grammar we just
showed for L2. But L1 is the intersection of context-free languages L2 and L3. We
can also show that the difference of two context free languages is not necessarily
context free. In fact we can prove something surprising. Intersection can be
expressed in terms of difference alone. Therefore any class of language is closed
under difference, it is also closed under intersection. The argument is that any,
the intersection of any two languages L and M, regardless of whether they're
regular context free or not context free, is the difference between L and L-M. That
is, suppose X is into L too second M. Okay, than X is surely. Not in L minus M,
because it's in both L and M. And therefore, X is in L, and not in L minus
M. Therefore, it is in this expression on the, on the right side. That proves
containment in one direction. For the other direction, suppose X is in L-L-M,
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
in l minus m, it must be, that x is also in m. Thus, X is in. L intersect M. That
proves containment in the other direction that is X here implied X there and that
proves the equivalence of these two expressions. Now suppose the class of
context free languages were closed under difference and L and M are context free
languages. Then L minus M would be context free and so would this guy, L minus L
minus M. But we just proved that this expression is the same as L intersect M,
thus context free languages would be closed under intersection but we know
they're not So we know that they cannot be closed under intersection but we know
they're not so we know that they cannot be closed under difference either. We know
that the intersection of two context free languages may not be a context free
language. However if we intersect a context free language in a regular
language then we always get a context free language. The idea is to run a DFA in
parallel with a PDA, since the DFA has not stack, we do not face the problem of
trying to simulate two stacks with one that we face Try to run two PDAs in
parallel. Here's the picture of a PDA and DFA running in parallel. We could combine
the states of the two automata to make one state for new PDA, it manipulates the
stack of the original PDA and feeds inputs into both the original PDA and the DFA. It
accepts if both the PDA and DFA accept. To give the construction of the new PDA let
the DFA have a transition function delta A and the original PDA will have a
transition function delta P. States of the new PDA will be pairs. The first
component, Q is a state of the DFA and the second component, P is a state of the PDA.
Suppose the original PDA has a choice of move from state P in stack symbol X, where
A is consumed from the input. That's this. A could be a real symbol or absolute. The
result of the move is that the PDA state becomes R and X on the stack is replaced
by Alpha. That's the move. Then they [inaudible] PVA who's transition function
we call simply delta. Given a state where P is the second component input A and
stack symbol X that's this. Has a [inaudible] of move where the new state
has second component R. The first component is what you get. By having the
dfa make a transition from state q with input A. That's delta A of q and A. It
could be [inaudible] here in which case delta A of q A is just q. Or it could be
real simple in which delta A of q A is something else. Finally this choice of
move replaces x by alpha on the stack. Just as the original pda did. The final
stage of the new pda is the [inaudible]. Such that Q and P are final states of
their respective [inaudible]. And the initial state of the new PDA is the pair
consisting of the initial states of both [inaudible]. We need to prove a pair of
inductions on the number of moves made by each PDA. These inductions say that the
new PDA started in its initial state with input W, this. Consumes the input, and
enters an ID with state QP. Okay, and stack alpha having consumed the input.
Okay, and that happens if and only if. The original PDA goes from its initial ID with
input W. To the ID with the same state P, and alpha on the stack. And of course the
DFA. Goes from it's initial state on input W to the state Q. Skip the details as the
proofs are not too hard.