The goal of this lecture is to show you the push on alternative to find exactly
the context for your languages. So let's get to it. Besides the comfort of knowing
that two seemingly unrelated concepts are really the same, the grammar PDA
equivalence will let us jump between the two notations when we talk about
properties of context free languages. The ability to jump between different
representations, regular expressions and deterministic [inaudible] was important
when we addressed properties of regular languages. Felicia found the ability
essential for context free languages as well. We also find it easier sometimes to
describe a PDA for a language rather than a grammar. For example, you might find it
hard to invent a grammar for balanced parenthesis, but a PDA is easy to think
of. Just push left parens onto the stack, and pop the stack, once, every time you
see a right parenthesis. If the bottom of the bottom of the stack marker is exposed,
then the parenthesis were balanced. And you never pop the bottom marker because
that would mean you have more right parens than left. Let's start with a language L
that has a context-free grammar G. We'll convert grammar G to a PDAP that accepts L
by empty stack. And if you want a PDA that accepts L by final state, we know how to
convert to one of those. P will have only one state, Q. That's all we need.
Naturally, Q is the start state. There are no final states because we are accepting
by empty stack. The input symbols of P are the terminals of G. The stacks symbols of
P are all the terms and variables of G. And the start symbol of P is the start
symbol of G. Our intent is that people step through a left-most arivation of
input W from the start symbol S. The secret is that each left [inaudible] form
is represented in a subtle way. It is whatever input P has so far consumed
followed by whatever is on P's stack. When P reaches an empty stack, then the
[inaudible] form it represents is whatever input it has consumed, followed by
nothing. That is, by the empty stack. That means that P has found a leftmost
derivation of the input string it has read. So acceptance of the string is
justified. If not sequence of choices of the nondeterministic P leads to empty
stack after consuming W from the input. And W is not a terminal string drive by
the grammar and P rightly does not accept W. There are two kinds of rules in the
transition function of P depending on whether a terminal or variable G is at the
top of P stack.The type one rules handle the case where A is the terminal on top of
P stack. There better NA as the next input symbol or P is guessed wrongly about the
left most derivation of the input as it actually exists. In affect we cancel the A
in the stack against the A on the input. The less intention form represented does
not change. We have now consumed one more input symbolA from the input. So that
becomes part of the left centential form. But the A that was at the stack top is
removed so it no longer participates in the left centential form. The type two
rules handle a variable, say A, at the top of the stack. We need to expand that
variable by the body of one of its productions, and thus, move to the next
[inaudible] form. Of course, we're only guessing. We have to allow any of A's
productions to be used. If A goes to alpha is one of these productions that a choice
for P, using epsilon input, and with A on top of the stack, is to replace A by
alpha. We're going to prove that P accepts exactly what G generates. Formally we will
show something more general. It seems we always have to show something more general
than what we really want. Here we show, that if p consumes w from its input.
Starting with only s on it's stack. And [inaudible] up with stack alpha That is
this ID becomes that ID.'Kay. Then in G, there is a left most derivation of the
screen W Alpha. Incidentally, notice that as we describe the moves of P, we allow
any string X to follow W on the input. Since no part of X was consumed, X cannot
have any effect on the moves P made reaching the ID shown, so if the statement
is true for one X, it is true for any other, that is X does not matter. We start
with the only if part. That is, if P makes the transition shown, then S derives W
alpha in G. The basis is zero steps and W is obviously Epsilon since nothing can
have been consumed from the input, and alpha is S since the stack doesn't change.
We need to show that S derives W alpha in a left most derivation. But W alpha is
just S and surely S derives itself. Now let's do the induction. We'll consider the
result of N steps of P, that is, this id has become that id and we'll assume the
inductive hypothesis. For sequences of N minus one steps. You must consider type
one and type two moves as a last step separately. For us consider the case.
Where the last of the n moves is a type one move. Where the a of the top of the
stack is canceled against the a on the input. Then the w consumed by the n move
system must then be formed y a. That's this. And before the last move, the Y was
consumed. That is, leaving just a X. Further, just before the last step. The
stack of P is A, alpha. But the inductive hypothesis applies to the first N minus
one moves, we can conclude that there is a left-most derivation from S of Y A alpha.
That's this and it corresponds to the fact that there is an N minus one derivation of
that ID. But Y A is W, so we already know that there is a leftmost derivation of W
alpha. That is the needed conclusion for the full sequence of N steps. Now, let's
look at the case of a type two rules, where there is a variable A on the top of
the stack, after the N- first move. After N-1 moves, P has consumed W from the
input, and has A beta on its stack. That's that. This, of course, is the ID after N-1
moves. At the nth move, no input is consumed but A is replaced by gamma, one
of its production bodies. Okay that is we assume A goes to gamma is A production,
okay notice that alpha is gamma beta here that is. This stack string is really,
alpha. Okay. Again we apply the inductive hypothesis to the first and minus one
steps. We thus know that there is leftmost derivation from this of WA Beta. Since A
is clearly the left most variable, and A goes to gamma as a production there is
also left most derivation of W gamma beta. That and of course gama beta is alpha so
that is really a derrivation of W alpha as we wanted to prove. We also should prove
the converse, but we won't. That is, we need to show if there's a leftmost
variation of W alpha. Is this, then peak at consumed W from its input with any
unseen X following. And turn stack S into stack Alpha. The proof is and induction on
the number of steps of the derivation but that's as far as we will take it. Assuming
we complete the proof of the converse, we have the statement we set out to prove. P
can consume W from its input with any X following, and turn stack S into stack
alpha if and only if G has a left most derivation of W alpha. Now we can restrict
the statement to what we really care about, the case where X is empty, that is,
P has consumed all its input, and alpha is also empty. That is, P has emptied its
stack and is accepted. We conclude that P consumes W while emptying its stack, if
and only if there's a left most derivation of W and G. That is W is in N of P, if and
only if W is in L of G. For our next trick, we'll show how to convert PDAs to
grabbers. Assume language L is accepted by PDAP by empty stack. If it were accepted
by a final state, we already know how to construct a new PDA that accepts L by
empty stack, so we're entitled to assume acceptance is by empty stack. We'll
construct G ground refer L, and the idea is to give G variables, which we'll denote
by PXQ with brackets around them, like this. His job, the job of this variable is
to generate [inaudible] only if the string's W. Such, that while reading W
from the input, P goes from state P to state Q, and appears to pop X from the
input. While doing so, P can grow the stack well above where X was. But it can
never go below where X was. And at the end, the stack is shorter by one than it
was when it started. That is the net effect is that X has been popped. Here's a
picture showing the height of the stack while X is effectively popped while
reading W. Note that X might be replaced at the first move or later by another
symbol, Y. It could even be replaced many times. But the position of the stack that
originally held X is never popped until the last move, right at the end here. As
we mentioned for every pair of states P and Q, and stack symbol X, there is a
variable that we represent by the composite symbol PXQ. Although this
expression consists of five characters, you must think of it as a single symbol,
in the set of variables of G. Also, as we hit to the java of PXQ, as it generate all
strings W that have the effect taking PDAP, and state P with only X on the stack
to the ID where the state is Q. The input has been consumed and X was popped. That's
that. Notice that since the initial landing shows nothing below X on the
stack. You know that X can't be pupped until the last step. So, PDAP can not make
any moves when it's stack is empty. And there's one more variable in gene that
starts in bolex. There maybe many productions of variable pxq. For each move
of the pda from state p with x as the top of the stack. We produce one or more
productions. There several cases and they get increasingly more complex depending on
how long the stack string is that's replacing x on the first move. The easiest
case is that of a rule that says, instate P with input A which could be epsilon or a
real symbol we pop X. That's that. Okay. Their x is replaced by zero symbols. Then
there is a production PXQ goes to A. The reason this is correct is that reading
only A is one way to have the metafact of popping X from going to state P to state
Q. The next simplest case is when a move replaces X by a string of length one, say
Y. Suppose that rule also changes the state to R. Then there's a production,
PXQ, goes to A R Y Q. That is, one way to pop X while going from state P to state Q
is to read input A going to state R and replacing the X by Y at the top of the
stack. Then, some number of inputs, AW, has the net effect of popping the Y while
going from state R to Q. As a consequence, the net effect of reading A followed by W.
Is to take state p, to state q while popping the original x. Here's a picture
of the case where x is replaced by a single symbol y. How the y gets popped, we
don't know, but when it does, the effect is that symbol a followed by whatever w
popped the y, has the effect of popping x while going from state p to state q. Now
it's getting a little more complicated. Supposed there is a move that replaces X
by two symbols Y ans Z, while going to state R and reading A from the input. As
the new stack YZ replacing X. In order for x to be raised. There must be some input
string u. That has the net effect of raising y. And you must take the pda from
state r to some state s. Which unfortunately we don't know. As a result.
We're going to have one production for each possible state s. But after reaching
state s. We must have some additional input [inaudible] that takes the pda from
state s to state q while popping the z from the stack. And that effect is that a
followed by u and then v pops x from the stack while going from state p to q.
Here's a picture of that action. Initially you see X got replaced by Y and Z on the
stack. Then U had the net effect of replacing Y, a pop, popping Y. Exposing
the Z, now we're in state S. And then V has the net effect of popping the Z and
winding up in state Q. So we generate many productions for this case, where I input
A, state P becomes R, and X gets replaced by the sta, on the stack by Y and Z. For
every state S, there's a production with head PXQ. And then the A that causes the
first move. Remember A could be empty. And then, RYS to effectively pop the Y,
winding up in the state S that we really don't know. So that's why there's one
production for each S. And then SZQ to effectively pop the Z. We finally wind up
in state Q, which is the state that we wanted to wind up, because that's the
state that appears in the head. As a result of this production you can see that
PXQ can derive any string AUV, provided that RYS derives the U. And SGQ divides
the V. In the general case, we're on input A, in state P. X is replaced by a string
of three or more stack symbols, Y1 through YK. And the state becomes r. We need a
family of productions in which there are k minus one unknown states, s one through s
k minus one, right. The productions all have this form. P X Q can re, can be
replaced by an A. Which again maybe esplon followed by variables R, Y1, S1. S1, Y2,
S2 and so on with the last of the variables being SK minus one, YK and
finally the state Q from the head that we want to wind up in. With productions
disrupted in this manner, we can prove that P accept W by empty stack, that is.
The I.D. Q0wz0 goes to P epsilon, epsilon, if and only if the variable Q0Z0P derives
W. We're not going to give the proof that is too easy inductions, one for each
direction. The only problem is, we don't know state P. But remember G has another
variable S and that is the start symbol. So, we add production S goes to Q0 Z0 P
for every state and now we have a grammar that generates exactly the strings that
the pdap accepts.