No Mixing and Matching

There may be several pairs that are options for a PDA in some situation. For instance, suppose S(q,a,X) = {{p,YZ), (r, e)}. When making a move of the PDA, we have to chose one pair in its entirety; we cannot pick a state from one and a stack-replacement string from another. Thus, in state q, with X on the top of the stack, reading input a, we could go to state p and replace X by Уor we could go to state r and pop X. However, we cannot go to state p and pop X, and we cannot go to state r and replace X by YZ.

T: A finite set of input symbols, also analogous to the corresponding component of a finite automaton.

Г: A finite stack alphabet. This component, which has no finite-autornaton analog, is the set of symbols that we are allowed to push onto the stack.

S: The transition function. As for a finite automaton, S governs the behavior of the automaton. Formally, 5 takes as argument a triple S{q, a, X), where:

1. 5 is a state in Q.

2. a is either an input symbol m 11 от a - e, the empty string, which is assumed not to be an input symbol.

3. X is a stack symbol, that is, a member of Г.

The output of Й is a finite set of pairs (p, 7), where p is the new state, and 7 is the string of stack symbols that replaces X at the top of the stack. For instance, if 7 = e, then the stack is popped, if 7 = X, tlien the stack is unchanged, and if 7 = YZ, then X is replaced by Z, and Y is pu.shed onto the stack,

qo: The start state. The PDA is in this state before making any transitions.

Zo: The start symbol. Initially, the PDAs stack consists of one instance of this symbol, and nothing else.

F: The set of accepting states, or final states.

Example 6.2: Let us design a PDA P to accept the language Liuttr of Example 6.1. First, there are a few details not present in that example that we need to understand in order to manage the stack properly. We shall use a stack symbol Zo to mark the bottom of the stack. We need to have this symbol present so that, after we pop ш off the stack and realize that we have seen wu> on the

6.1.3 A Graphical Notation for PDAs

The list of S facts, as in Example 6.2, is not too easy to follow. Sometimes, a diagram, generalizing the transition diagram of a finite automaton, will make aspects of the behavior of a given PD.\ clearer. We shall therefore introduce and subsequently use a transition diagram for PD.A.s in which:

a) The nodes correspond to the states of the PD..

b) An arrow labeled Start indicates the start state, and doubly circled states are accepting, as for finite automata.

c) The arcs correspond to transitions of the PDA in the following sense. An arc labeled a, A/n from state q to state p means that d{q.u.X) contains the pair (p, a), perhaps among other pairs. That is, the ;irc label tells what input is used, and also gives the old and new tops of the stack.

input, wo atiil have something on the stack to permit us to make a transition to the accepting state, 92- Thus, our PDA for Lut can be described as

/ = ({9о,9ь?2},{0.1}.{0-1.2п},й,<7о,-го,{72}) where Л is defined by the following rules:

1. <5{<7().O.Zo) = {(?o,OZo)} and 6(90.l,Zo) = {((/оДо)}. One of these rules apilies initially, when we are in state qo and we see the start symbol Zo at the top of the stack. We read the first input, and push it onto the stack, leaving Zo below to mark the bottom.

2. %r 0.0) = {((/0,00)}, (90,0,1)-{(/0,01)}, 1,0)-{(9(1,10)}, and S{qoy 1; 1) = {{Qo, !!)} These four, sinular rules allow us to stay in state qo and read inputs, pushing each onto the top of the stack and leaving the previous top stack symbol alone,

3. 5((ft f,if)) - {(71,Zo)}, S{qo,e,0) = {(/ 0)}, and (0,,1) - {(f/i,l)}. These three rides allow P to go from state qo to state 51 spontaneously (on f input), leaving intact whatever symbol is at the top of the stack.

4. (5(1,0,0) - (<ji,f)}, and (i (vi-1-1) - {(Уь)}- Now, in state 91 we can match input symbols against the top symbols on the stack, and pop when the symbols match.

5. 6(qi.e. Zq) - {(q2, Zu)} Finally, if we expose the bottom-of-stack marker Zo and we are in state q. then we have foimd an input of the form ww. We go to state (72 and accept.

□

0, Zo/OZo

1, Zq/IZo 0 , 0/0 0

0 , 1/0 1

1,0/10 0 , 0 / e

1,1/11 1, 1 / e

-©-

£, Zq /Zq e , Zq /Zq

£,0/0

e, 1 / 1

Figure 6.2: Representing a PDA as a generalized transition diagram

The only thing that the diagram does not tell us is which stack symbol is the start symbol. Conventionally, it is Zq, unless we indicate otherwise.

Example 6.3: The PDA of Example 6.2 is represented by the diagram shown in Fig. 6.2. □

6.1.4 Instantaneous Descriptions of a PDA

To this point, we have only an informal notion of how a PDA computes. Intuitively, the PDA goes from configuration to configuration, in response to input symbols {or sometimes c), but unlike the finite automaton, where the state is the only thing that we need to know about the automaton, the PDAs configuration involves both the state and the contents of the stack. Being arbitrarily large, the stack is often the more important part of the total configuration of the PDA at any time. It is also useful to represent as part of the configuration the portion of the input that remains.

Thus, we shall represent the configuration of a PDA by a triple (g,w),7), where

1. gr is the state,

2. w is the remaining input, and

3. 7 is the stack contents.

Conventionally, we show the top of the stack at the left end of 7 and the bottom at the right end. Such a triple is called an instantaneous description, or ID, of the pushdown automaton.

For finite automata, the 6 notation was sufficient to represent sequences of instantaneous descriptions through which a finite automaton moved, since