There is a pumping lemma for context free
languages analogous to the pumping lemma
for regular languages. The goal of this
lecture is to [inaudible] improve this
lemma, which is naturally more complicated
than the pumping lemma for regular
languages. And then use it to show certain
languages are not context free. Let's
review the pumping lemma for regular
languages. It said that any sufficiently
long string W in a regular language has
some short non empty piece near the
beginning that we could pump. That is, we
could repeat it as many times as we liked,
including zero. And the resulting stream
would also be in the language. We found
the strength of pump by looking for the
first state to repeat as a finite
automaton process that's input W. The
pumping level of a context free language
says that we can find two pieces in any
long string Z and pump them in tandem.
That is, we can repeat each of them I
times or any I equal to the greater than
zero, and the result will be in the same
language. We'll also see that these two
strings are close together in Z, and one
can be empty but not both. Here's the
statement of the ? For context free
languages. We can see it as the same sort
game with an adversary that we talked
about in connection with regular
languages. For every context free language
L, that is you get to pick L presumably
the one you want to show isn't really
context free, there's an integer N. This
is something the adversary gets to pick
but once it's picked it's fixed for the
rest of the game. Such that for every
string Z and L of length at least N And
here, you get to pick the Z to focus on.
You can break Z into five pieces - U, V,
W, X, Y, such that three things are true.
The adversary gets to pick how Z is
broken, but subject to two constraints
we'll see in just a moment. And
incidentally, V and X are the substrings
that get pumped. The first constraint is
that the middle three component, V, W, and
X are short, no longer than the length of
them put together. Remember that V and X
will get pumped, so that's a. Not only are
they short but they appear within a
bounded distance from each other within Z.
The second condition that the adversary
has to respect is that V and X cannot both
be empty, although one can. And if all the
above is satisfied and L really is context
free then for all integers I equal to or
greater than zero: U, V to the I, W, X to
the Y, Y is also an L. We win the game and
prove is not context free by allowing the
adversary's choices of N and. Breakup of
Z, subject to the constraints one and two.
And then picking an I, such that UV to the
IW, X the IY is not an L. The proof the,
the pumping lemma for context free
languages starts with a [inaudible] normal
form grammar for L. Technically, it is for
L minus epsilon, but the empty string will
never meet the condition of being of
length at least N. So its presence of
absence doesn't matter. The [inaudible]
grammar has M variables for sub M. So
we're going to let M be two to the M. And
now lets consider any string, z and l, of
length at least n. That's two to the m
again. We're going to prove first that any
[inaudible] tree in the c and f grammar,
for string z of length at least n equals
two to the m, must have a path of length m
plus two or more from the root to a leaf.
Well, actually. Proof the contra-positive.
That is, suppose there's a parse tree Z
with no path longer than M plus one. Such
a path has M nodes labeled by variables at
the top, or the beginning, and one node
labeled by a terminal at the end. That is,
here is a typical path. That is, here is a
typical path. It will have variables here,
here, and here and then a terminal there.
Okay. If we forget about the terminals at
the leaves. Part strain at CNF grammar is
a binary tree. Let's say at each level the
number of notes is almost gonna double.
Thus there is only one note at the top
level, the root, there can be only two
notes at the next level four at the third
and eight at the fourth and so on. In
general there will be at most two to the
power M -one at the end level. But this
tree has it most m levels with variables
and then along each. Variables. The last
variable has one trial with a terminal as
its label. The largest number of leaves
occur if all the paths on the tree have
exactly N variables. If some paths
terminate before level N, there will be
fewer leaves. Thus there are at most two
to the N minus one nodes that are labeled
by variables and have a single trial with
a terminal label. And thus there are at
most two to the N minus one leaves.
Finally, we therefore can conclude that
the length of the yield is at most. Most
of the two to the M minus one power M
minus one. [inaudible] Power of m minus
one is n over two. So z is of length n
that cannot be the yield of any three.
That has passed limited to length m plus
one or less. Therefore, we conclude that
somewhere on the [inaudible] is the path
of this m plus two. Now we're ready to
prove the pumping level. We just proved
that Z's parsed tree has a path of length
at least M+2. Only the last [inaudible] on
any path can be labeled by a terminal. So
there are at least M+1 [inaudible] with
variables along this path. Let's focus on
one of the longest paths on the. Surely
there are at least ten plus one variables
along this longest path. Remember that M
is the number of variables of the grammar.
So, along this path, there are two low
nodes labeled by the same variable, call
it A. In fact, to make sure we pump short
pieces, let's look only at the bottom most
M+1 variables along this path, which could
be much longer than M+1. And we know that
two of them must be the same. On the next
slide we'll see what the pause stream must
look like. Here's the picture of the
[inaudible] tree for z. We've showed the
path we've focused on and the lowest
repeating variables along that path. The
purple tree is rooted at the lower a. And
the yellow tree with the purple tree
within it is rooted up at upper a. Let W
be the yield of the purple tree. V and X
the portions of the yield with the yellow
tree that precede and follow W
respectively. And let U and V be the
portions of Z that precede V and follow X
respectively. Let's look at the yellow.
Since the path shown is as long as any
other, and that path has at most N+1
variables, we know by the lemma one that
we just proved that the yield of the
yellow plus purple is no longer then two
to the power M or N. That is, the length
of VWX is no more than N. But v and x both
can't be empty. Why? That's a useful
property of [inaudible] normal form of
grammars. Since the two A's shown in the
tree are different nodes, the upper A must
have a child to the left or right of the
path shown. That's a consequence of the
fact that we eliminated unit production so
all bodies that have variables have at
least two of them. Moreover, once we have
a variable not on the path, there are no
epsilon productions so we must generate
from this variable at least one terminal.
That is all we need to conclude that
either V or X or both have length at least
one. Now we can take advantage of the fact
that we have two As along the path. We can
get rid of V and X by pumping zero times.
That is, we know the purple tree can
substitute for the yellow because both
trees have the same variable A at the
root. If the original on the left
satisfies the conditions of a parse tree,
that is, every interior node is the head
of a production whose body is the labels
of his children, then the same will be
true of the smaller parse tree on the
right. We conclude that UWY is also in the
language. Well, we could pump twice, that
is, replace the purple tree by the yellow
which has the purple within it and you get
a par [inaudible] whose yield is uvvwxxy.
And in the previous tree representing
pumping twice, we could again replace the
purple tree by the yellow, and get a
bigger tree, whose yield is U, three V's,
W, three X'es, and then Y. In the same
manner, we could get parse trees for all
strings [inaudible] form. U, V to the I,
W, X, the IVY, for any integer I equal to
or greater than zero. These strings are
therefore all in the language L. That
proves the pumping [inaudible] for context
free languages. Let's look at an example
of how the pumping [inaudible] can be used
to show a language not to be context free.
This language which involves matching the
counts of two blocks of zeros is context
free. A grammar of PDA4 is easy to
construct. The ideas are very much like
what we saw for the language O to the N,
one to the N. But give the language three
blocks of zeros, all of which must be the
same length and we're suddenly outside
what context free grammars can do. We can
prove that using the problem for
context-free languages. So we'll pick this
language L. And the adversary now gets to
pick N. We don't know N, but we do know
it's fixed for the rest of the game. We
get to pick Z, so let's pick zero to the
N, one, zero to the N, one, zero to the N.
That is, each block of zeroes is of length
equal to whatever N the adversary picked.
Now the adversary gets to break I, G up
into Z equals U, V, W, X, Y. But he must
chose these substrings, such that DWX
together are no longer than N and D and X
can not both be picked to be the empty
string. There two cases depending upon
whether the advisory picks D and X to have
zeros or not. The first case, suppose
there are no zeros among D and X and since
they can not both be empty. There must me
at least one, one among them. But then if
we pump zero times to get the string UWY.
We know that there is at most one, one in
this string. The pumping number claims it
as in the language l. But it can't be,
because all strings in l have exactly two
1s. In the second and last case, v and x
have exactly one zero among them. D W X
has length at most N. So these three sub
strings cannot extend from the first block
of 0s to the last because N plus two
positions separate those blocks. So again
consider U, W, I which if L is context
free it must be an L. Removing V and X
must leave at lease one of the three
blocks of N 0's intact, so it still has N
0's but V and X have at least one zero so
when U, W, Y at least one of the blocks of
0's is fewer than N 0's. We conclude that
in this case too U, W, Y cannot be an L
and those L cannot be context free.