Today, we're going to see an automaton
that is the equivalent in power to the
context free grammar. The equivalence is
analogous to the equivalence between
regular expressions in automata, epsilon
NFAs in particular. The automaton is
called the push down automaton, or PDA. A
term that was in use long before there
were personal digital assistants. After
describing the mechanics of the PDA we'll
talk about two different but equivalent
ways that PDAs can define a language.
We'll also mention the deterministic PDAs
since the standard model of the PDA is the
non-deterministic version with epsilon
transitions allowed. One of the key points
to remember is that PDAs define all and
only the context free languages. But
unlike [inaudible], the non deterministic
version is strictly more powerful than the
deterministic version. And only the
non-deterministic version defines the
class of context free languages. However,
the deterministic version is quite
important in compiling. Since parses for
programming languages usually behave like
a deterministic BDA. Most programming
languages are designed to be recognized by
deterministic PDA. For example we
mentioned previously the class of [laugh]
[inaudible] one grammars and such a
grammar can be converted easily to a
deterministic PDA. We'll get to a formal
definition of a PDA shortly. But to start
think of the PDA as an epsilon NFA with an
additional stack on which you can store
symbols. Like any stack you can only see
the top symbol. The next move of the PDA
is a function of three things. The move
can depend on the state it is in, just
like a finite automaton. The move also
depends on the next input symbol, or the
PDA may make a move on epsilon that is
without regard to the next input symbol.
This behavior is exactly like that of the
epsilon NFA. But the thing that make the
PDA different from the final automaton is
that it has a stack of symbols chosen from
a finite alphabet, and it can use the top
symbol to help decide on the next move to
make. Here's the image of a PDA we should
keep in mind. At the center is the state.
Like the state of the [inaudible] it
controls what happens. Here's an input
which is waiting to be processed by the
PDA. The PDA can only see the next input
symbol and can use the symbol to help
decide the next rule. It also has the
option to make a move on the abs long
without consulting the input and they has
a stack of symbols. It can see only the
top symbol and use that to help choose
next rule. Moves of the PDA can involve a
change of state, like the [inaudible]
automaton. But it can also push or pop the
stack. In any situation that is, is some
state, with some next input and some
[inaudible] stack, the PDA has a finite
number of choices of next move. Since it
is non-deterministic, it is perfectly
acceptable for it to be more than one
choice. A move choice consists of a change
in state which could of course be to the
same state it is in. A manipulation of the
stack. And each move, the top stacks
[inaudible] is replaced by a string of
stack symbols. If the string is empty, it
has the effect of popping the stack. If
the string is of length one, then the top
stack symbol can be changed or not, since
the replacing symbol can be the same as
the original. If the replacing string has
length K greater than one, we can see them
move as a change of the top stack symbol,
followed by K minus one pushes of symbols.
Now we'll give the formal notation and
usual symbols for the components of the
PDA. There is a finite set of states for
which we tend to use Q. Just as for finite
atomata. There's a finite input alphabet
for which we'll continue to use sigma.
There's a finite stack alphabet. Symbols
that can appear on the stack. For this
alphabet we use gamma. There's a
transition function delta to be described
shortly. There's a starred state,
typically Q0 as finite atomata. There is a
starred symbol. This symbol is a member of
the stack alphabet and initially the stack
contains only this symbol. And there is a
set F of final states again analogous to
the finite atomata. There are conventions
for PDAs that are analogous to the
conventions we made for [inaudible] and
[inaudible] previously. We continue to use
lower case letters at the beginning of the
alphabet for input symbols. However, for
PDAs it is sometimes convenient to allow
these letters to stand for epsilon as well
the symbols of the input alphabet. Capital
letters at the end of the alphabet are
stack symbols. Lower case letters at the
end of alphabet are strings of input
symbols. Greek letters at the beginning of
the Greek alphabet are strings of stack
symbols. We always write stack strings
where the tops of stack is at the left
end. The transition function for PDA has
three arguments. The third argument is the
symbol at the top of the stack. First
comes the state, as we find at Atomana.
Second, an input symbol or epsilon as for
the epsilon in a phase transition
function. And last the stack symbol. Delta
for state Q, input A, which can be
epsilon, and stack symbol Z, is a set of
zero or more actions. Each action consist
of a next state P and a string alpha of
stack symbols possibly empty with which to
replace the top symbol Z. To summarize,
when delta of q A and [inaudible] contains
p alpha. Then one choice of move for the
pda when it is in state q. Sees A at the
front of the remaining input and has z on
top of stack. Is to go to, to state p,
remove A from the front of the input. Of
course, if A is [inaudible]. Then the
remaining input doesn't change. And
replace Z by alpha on top of the stack.
Note that although the pda may have
choices. Several different p alpha pairs.
It has to pick one pair and then do both.
Things associated with that pair. It can't
pick a next state from one pair, and a
stack string from another. Let's design
the PDA for our favorite context free
language. The set of strings are the forms
zero to the N, one to the N. Okay? We need
three states, Q will be the start state.
It represents the condition that we've so
far seen only zeros on the input. B is the
state that we go to first when we see the
first one. We use the states to remember
not to accept the string if we see anymore
zeros. And f will be the final state. It's
there only so we can accept if the numbers
of 1s match the number of 0s. We also need
two [inaudible] symbols. Z zero was the
star symbol. It has an important job.
Marks the bottom of the stack. As we read
zeros on the input. We will push one x on
to the stack for each zero we read. As
ones come in we pop one x for each one. So
in the bottom mark, the zero again becomes
the top stack symbol. We know we've seen
exactly as many ones as they were zeros.
So we accept. >> Here's the transition
function of our PDA. >> Hm. Initially, Z
zero is at the top of the stack. When we
see the first zero, we push an X onto the
stack. Notice that the replacement string
is XZ zero, it's that. That string
replaces Z zero, but the net effect is
that Z zero remains, and X is pushed onto
the top. Remember that stat strings are
written with the top at the left. We
remain [inaudible] as long as zeros remain
on the input. After the first zero, each
additional zero causes the x on top of the
stack to be replaced by two x's. Thus, the
number of x's on the stack always equals
the number of zeros read from the input.
When a one appears at the front of the
input, if x is on top of the stack, then
we go to state b and pop the top x. Notice
that there has to be an x on top of the
stack so if the first input is one, when
we still have z zero on top of the stack
we have no move at all, and, and never
accept. As long as more 1's appear on the
input we stay in state P., and pop an X.
From the input. Thus after seeing N. 0's
followed by M. 1's, the number of X's
remaining on the stack will be N. Minus M.
And thus after seeing N0 followed by
exactly N1s there are no more Xs on the
stack and the top symbol becomes Z0 again.
The last move of this PDA says that if we
are in state P with Z0 on top of the stack
then without using any input we go to
state F. Z0 remains on the stack although
that is not important. Here's a moving
picture of the PDA we designed. With
000111 waiting on the input. Initially its
with state Q. With just ZO on the stack.
That's the initial configuration. For the
first move we consume the first zero from
the input and replace Z0 by XZ0 on the
stack. Notice the X is on top of the Z0.
It's at the top of the stack. We consume
another zero and replace the top X by two
Xs, and the same thing happens again. Now
the first one is consumed from the input.
We transition to state P and [inaudible]
the top X. Staying in stay P, we consume
another one and pop another X, same thing.
Now all the input is gone, but we have Z
zero on top of the stacks, so with epsilon
input we can go to state F and accept.
We're done. And we accepted the input
string that was consumed, 0,0,0,1,1,1. To
talk more formally about the behavior of a
PDA, we need the notion of an
instantaneous description, or ID. The ID
tells us the current state Q, the
remaining input W, and the stat contents
Alpha. Again remember that the top of the
stack will be the left most symbol of
alpha. There is an analogy between
derivations for grammar and sequences of
ID's for PDA. The ID's are analogist to
the sentential form to the grammar. In
place of the double arrow we use the turn
style symbol that's this. To express the
idea that one IDI can become another IDJ
by one move of the PDA. That is, suppose
the first ID has state Q. And input AW,
where A is either the first symbol or
epsilon, whatever is used for the next
move. And it has stack X alpha. Where X is
the top symbol and alpha is then
everything below that. Suppose the delta
of QAX contains P beta. Then a possible
next id has state P, which is this. W is
reigning on the input because A got
consumed and A maybe a symbol or an
[inaudible] doesn't matter. And, beta
alpha on the stack where the x here got
replaced by beta. We also have a goes to
star relation for i.d.s defined
analogously to the way we defined arrow
star for centenral forms. That is the
basis representing zero moves says that
any ID goes to star itself. And for the
induction, if I goes to J by some number
of moves, possibly zero, and J goes to K
by one move, then I goes to K by some
number of moves. Here's the sequence of
IDs that we get from our previous example.
The input is 000111, so the initial ID has
state Q, that input, and stack Z zero.
Here it is. The first move consumes the
zero from the input, and pushes X onto the
stack. So this zero got consumed, that's
what's left, and, of course, the X zero,
XZ zero is now on the stack. The second
and third moves do the same. And you can
see additional x's being pushed onto the
stack. Okay. Next because, the next input
is one, the state becomes P and the one is
removed from the input. Also an X is
popped. And that explains that ID. And two
more moves pop the remaining X's, it's
that and that. And then, in the final ID,
the state P has become F. And we accept.
We can summarize the sequence by saying
that the initial ID, this. Goes to star
the final ID. That, we can also say that
any of these IDs goes to star itself and
also to any of the IDs that follow in the
sequence we just showed you. In order to
understand better the idea of acceptance
of an input by a PDA, we have to ask
ourselves, what would happen if there were
an extra one on the input? We'll take that
up on the next slide. Okay, the sequence
of ideas is the same, except that an extra
one tags along at the end of each input
string. The last move, where the state
changes from P to F, is still legal,
because a PDA can use epsilon input even
if there is input remaining. [sound].
State F has no transitions so the sequence
cannot be extended and the last one can
never be consumed. We conclude that 0-0-0
followed by four 1's is not accepted
because the input was not completely
consumed even though we entered the final
state in the middle of the process of
consuming the input. Okay. The normal way
to define the language of the P.D.A. Is by
final state. That is, L. Of P. The
language of the P.D.A.P. Is the set of
strings W. Such as that when P. Is started
in its start state. The W on the input and
the start symbol on the stack that's this,
ID. There is a sequence of moves that
[inaudible] leaves to an ID with a final
state. There we are. With w completely
consumed. It's that and anything on a
stack. I don't care. However there is
another way to define the language of a
pda. And this approach turns out to be
rather useful. Especially when we show how
to convert pdas to grammars and visa
versa. We can talk about the set of
strings that make the pda empty it's
stack. This language is conventionally
called BFP for pdap. The n stands for null
stack although we're not going to use that
term. Formally, this language is the set
of strings W, [inaudible] started in the
usual ID with input W. That's, of course,
this. P eventually reaches an ID in which
it has consumed all of W, and its stack is
empty. Okay, we don't care about the state
Q, it can be final or non final, doesn't
matter. Thus, every PDA defines two
different languages in two different ways.
However, the classes of languages defined
by all the PDAs in these 2As are the same.
And, in fact, the context free languages,
as we should see later. That is, if we
have a PDAP that defines a language L by
final state, then there's another
different PDAP prime that defines the same
language L, but does so by empty stack. P
prime will presumably define a different
language by a final state, but that
doesn't matter. The point is that every
language defined by final state, by some
PDA, is also defined by empty stack by
some PDA. And conversely if a language L.
Is defined by some P.D.A.P., by empty
stack, then L. Is also defined by some
P.D.A.P. Double prime, by final state.
Here's a rough idea of how we can work a
PDAP accepting L by final state to P prime
accepting L by MP stack. Basically P prime
will simulate P, that is it does what P
does with a few exceptions. If P prime
finds that P is accepted by entering a
final state, P prime empties its stack.
Since P and P prime are in general
non-deterministic P prime can also guess
that P will read more input, P prime will
then not empty its stack in that sequence
of moves. But rather will continue
simulating P. But since P. Prime accepts
whenever it empties its stack, and P.
Might do that on inputs it doesn't want to
accept. P. Prime needs a bottom of the
stack marker to prevent it from
accidentally emptying its stack during the
simulation of P. Plus, we'll give P prime
all the state symbols and moves of P, in
order to do the simulation of P. Plus a
few other bells and whistles, which we'll
explain next. First P prime has a stack
symbol at zero. This is the start symbol
of P prime. And it also has the job of
guarding the stack bottom against
accidental emptying. That is if P empties
its stack, P prime will find a zero on top
of its stack and realize that P can make
no move from this ID. Although being under
terministic, it may have other ways to
proceed. P prime thus does not empty its
own stack. B prime has a new start state S
and an erase state E. P prime has several
additional transitions. This rule. Says
that in its additional ID it has only one
choice. It must change from its start
state of p and push z-zero, p's start
symbol on top of its own start symbol,
x-zero. Which remains to guard the stack.
P prime is now ready and able to simulate
p. Until p accepts, all the moves of p
prime are the same as the moves of p. With
the guard x zero sitting at the bottom of
the stack, but unseen. And if p prime
enters any final state f of p. Then it
enters the erase state E, and it popped
its stack without reading any more input.
Moreover, in the erase state E, it also
has only the choice of [inaudible] popping
the stack and staying in state E.
Eventually, P prime empties its stack and
accepts. Now let's explain the
construction in the opposite direction.
That is [inaudible] accepts some language
by empty stack. And we must design P
double prime to accept the same language
but by final state. P double prime also
stimulates P with a few bells and
whistles. First, P double prime needs a
bottom marker to detect that P has emptied
its stack. If P double prime sees this
marker at the top of the stack after its
initial move then it knows that it has
emptied its stack and so P double prime
must accept by entering its own final
state. P. Double prime has all the states,
symbols, and transitions of P. In
addition. P. Prime has a new start symbol
X. Zero that also guards the stack bottom
just like it does for P. Prime. P Double
Prime has a new start state S and a new
final state F. From the ini-, the initial
ID. A P. Double prime goes to the start
state of P., and pushes the start symbol
of P. Onto it's own stack. It is thus
ready to simulate, P. Once in the states
of P., if P. Double prime ever sees the
guard X. Zero at the top of the stack, it
knows P. Is accepted. P double prime
therefore goes to its own final state.
[inaudible] Without reading anymore input,
and therefore accepts by final state the
input that P accepted by empty stack. And
a final word about the deterministic PDA.
In order that there never be a choice of
move, we certainly want the PDA to have,
at most, one choice of move for any state
Q, input symbol A, including epsilon, and
stack symbol X. But we also have to rule
out the possibility that there is a choice
between using a real input symbol and
making a move on epsilon. To be precise,
for no q and x can both delta of qax and
delta of q epsilon x be nonempty. Such a
PDA can have only one sequence of ID's.
Starting from the initial id with a given
input stream. We, generally, assume
acceptance is by final states and if you
accept by emptying your stack you cannot
ever process any more input if you're
deterministic. Well, we shall not expand
on the matter the placid language is
accepted by deterministic bda's, contains
all the regular languages obvious since it
cam simulate a deterministic finite
automaton by just ignoring its stack. But
it does not include all the context free