the ID for a finite automaton is just its state. However, for PDAs we need a notation that describes changes in the state, the input, and stacl<. Thus, we adopt the turnstile notation for connecting pairs of TDs that represent one or niany moves of a PDA.

Let P = iQ,E.r,5,qo,Zo,F) be a PDA. Define h , or ju.4t h лvhen P is

understood, as follows. Suppose d{q,a,X) contauis (p,a). Thou for аП strings w in S* and 3 in Г*:

{q,aw.,X,3) h {p,U3.a(3)

This move reflects the idea that, by consuming a (which may be e) from the input and rei)lacing X on top of the stack by q, we caii go from state q to state p. Note that what remains on the input, w, and what is below the top of the stack, do not influence the action of the PDA; they are merely carried along, perhaps to influence events later.

We also use the symbol h , or when the PDA P is understood, to represent

zero or more moves of the PDA. That is: BASIS: / / for any ID i.

INDUCTION: ir ,/ if there exists some ID К such that / h К and К P J.

That is, 7 J if there is a sequence of IDs Al, A2,... ,iC such that 1 - lii, J - K , and for all i - 1,2,..., n - 1, we have Kj \- A,.l.

Example 6.4: Let us consider the action of the PDA of Example 6.2 on the input 1111. Since qo is the start state and Za is the start symbol, the initial ID is (go, 1111, Zi,). On this input, the PDA has an opportunity to guess wrongly several times. The entire .sequence of IDs that the PDA [:an reach from the initial ID (ijo, 1111, Zo) is shown in Fig. 6.3. Arrows represent the I- relation.

From the initial ID, there are two choices of move. The first guesses that the middle has not been seen and leads to ID {qa, Ш, IZo). In eflect, a 1 has been removed from the input and pushed onto the stack.

The second choice from the initial ID guesses that the middle has been reached. Without consuming input, the PD.\ goes to state qi, leading to the ID (gi, 1111, Zq). Since the PDA may accept if it is in state qi and sees Zq on top of its stack, the PDA goes from there to ID (72, HH, Za)- That ID is not exactly an accepting ID, since the input has not been completely consumed. Had the input been e rather than 1111, the .same sequence of moves would have led to ID {q-2,€-: Zo), which would show that e is accepted.

The PDA may also guess that it has seen the middle after reading one 1, that is, when it is in the ID (</(j, lll,lZo). That guess also leads to failure, since the entire hiput cannot be consumed. The correct guess, that the nuddle is reached after reading two Is, gives us the sequence of IDs (qo,lUl, Zq) (-(?u,llLlZo) f- iqo.MMZo) h (g ll,llZo) h (quhlZo) h (f/ f,Zo) h ((I-2,e,Zo). □

There are three important principles about IDs and their transitions that wc shall need in order to rea.son about PDAs:

( 0 , 111, IZq ) { q, llll.Zo ) ( 92 lllbo )

( 9o , IMIZq ) ( , lll,lZo ) ( .n,Zo)

I.IUZq) (j, 11,11Zo) (?2.11,Zo)

( , e,nilZ(j) ( , e,UZq) {q, г, Zq) Figure 6.3: IDs of the PDA of Example 6.2 on input 1111

1. If a sequence of ГОд {computation) is legal for a PDA P, then the computation formed by adding the same additional input string to the end of the input (second component) in each ID is also legal.

2. If a computation is legal for a PDA P, then the computation formed by adding the same additional stack symbols below the stack in each ID is also legal.

3. If a computation is legal for a PDA P, and some tail of the input is not consumed, then we can remove this tail from the input in each ID, and the resulting computation will still be legal.

Intuitively, data that P never looks at cannot affect its computation. We formalize points (1) and (2) in a single theorem.

Notational Conventions for PDAs

We shall continue using conventions regarding the use of symbols that we introduced for finite automata and grammars. In carrying over the notation, it is useful to realize that the stack symbols play a role analogous to the union of the terminals and variables in a CFG. Thus:

1. Symbols of the input alphabet will be represented by lower-case letters near the beginning of the alphabet, e.g., o, b.

2. States will be represented by q and p, typically, or other letters that are nearby in alphabetical order.

3. Strings of input symbols wiU be represented by lower-case letters near the end of the alphabet, e.g., w or 2.

4. Stack symbols wfil be represented by capital letters near the end of the alphabet, e.g., X or Y.

5. Strings of stack symbols wiU be represented by Greek letters, e.g., ex or 7.

Theorem 6.5 : If P = (Q, S, Г, 5, qo: Zq, F) is a PDA, and (q, x, a) \ (p, y, /3), then for any strings vj in S* and 7 in Г*, it is also true that

{q,xw,aj) {p,yw.,8l)

Note that if 7 = e, then we have a formal statement of principle (1) above, and if Ш = e, then we have the second principle.

PROOF: The proof is actually a very simple induction on the number of steps in the sequence of IDs that take {q,xw,ay) to (p,yvj,l3y). Each of the moves in the sequence {q,x,a) {p,y,(3) is justified by the transitions of P without

using w and/or 7 in any way. Therefore, each move is still justified when these strings are sitting on the input and stack. □

Incidentally, note that the converse of this theorem is false. There are things that a PDA might be able to do by popping its stack, using some symbols of 7, and then replacing them on the stack, that it couldnt do if it never looked at 7. However, as principle (3) states, we can remove unused input, since it is not possible for a PDA to consume input symbols and then restore those symbols to the input. We sta,te principle (3) formally as: