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