BASIS: One move. The only possibility is that A -> e is a production of (3, and this production is used in a rule of type (1) by the PDA P. In this case, x = c, and we know that A c.

INDUCTION: Suppose P takes n moves, where n > 1. The first move must be of type (1), where A is replaced by one of its production bodies on the top of the stack. The reason is that a rule of type (2) can only be used when there is a terminal on top of the stack. Suppose the production used is A -¥ Y1Y2 -Yk, where each Yi is either a terminal or variable.

The next тг - 1 moves of P must consume x from the input and have the net effect of popping each of Yi, Y2, and so on from the stack, one at a time. We can break x into xiX2---Xk, where xi is the portion of the input consumed until Yi is popped off the stack (i.e., the stack first is as short ask -I symbols). Then X2 is the next portion of the input that is consumed while popping Y2 off the stack, and so on.

Figure 6.9 suggests how the input x is broken up, and the corresponding effects on the stack.. There, we suggest that /3 was BaC, so x is divided into three parts хтХ2Хз, where X2 - a. Note that in general, if Yi is a terminal, then Xi must be that terminal.

Figure 6.9: The PDA P consumes x and pops BaC from its stack

Formally, we can conclude that (9,XiXi+i x, Vj) 1 {q, -, e) for all i - 1,2 .., fc. Moreover, none of these sequences can be more than n - 1 moves, so the inductive hypothesis applies if 1 is a variable. That is, we may conclude Yi Xi-

If Yi is a terminal, then there must be only one move involved, and it matches the one symbol of Xi against Yi, which are the same. Again, we can conclude

If Xi] this time, zero steps are used. Now we have the derivation

X1X2 Xk

That is, A X.

To complete the proof, we let A - 5 and x - w. Since we are given that w is in N{P), we know that {q,w,S) (д,б,б). By what we have just proved inductively, we have S w; i.e., w is in L{G}. □

6.3.2 From PDAs to Grammars

Now, we complete the proofs of equivalence by showing that for every PDA P, we can find a CFG G whose language is the same language that P accepts by empty stack. The idea behind the proof is to recognize that the fundamental event in the history of a PDAs processing of a given input is the net popping of one symbol off the stack, while consuming some input. A PDA may change state as it pops stack symbols, so we should also note the state that it enters when it finally pops a level off its stack.

Figure 6.10: A PDA makes a sequence of moves that have the net effect of popping a symbol off the stack

Figure 6.10 suggests how we pop a sequence of symbols Y-Y,.. .Yk off the stack. Some input xi is read while Y is popped. We should emphasize that this pop is the net effect of (possibly) many moves. For example, the first move may change Y\ to some other symbol Z. The next move may replace Z byUV, later moves have the effect of popping U, and then other moves pop V.

The net effect is that Yi has been replaced by nothing; i.e., it has been popped, and all the input symbols consumed so far constitute Xi.

We also show in Fig. 6.10 the net change of state. We suppose that the PDA starts out in state po, with Yi at the top of the stack. After all the moves whose net effect is to pop Yi, the PDA is in state pi. It then proceeds to (net) pop Y2, while reading input string xa and winding up, perhaps after many moves, in state P2 with Y2 off the stack. The computation proceeds until each of the symbols on the stack is removed.

Our construction of an equivalent grammar uses variables each of which represents an event consisting of;

1. The net popping of some symbol X from the stack, and

2. A change in state from some p at the beginning to q when X has finally been replaced by e on the stack.

We represent such a,variable by the composite symbol [pATt/]. Remember that this sequence of characters is our way of describing one variable; it is not five grammar symbols. The formal construction is given by the next theorem.

Theorem 6.14: Let F {Q, E, Г, 5, qo, Zq) be a PDA. Then there is a context-free grammar G such that L{G) = N{P).

PROOF: We shall construct G = {V,E,R,S), where the set of variables V consists of:

1. The special symbol S, which is the start symbol, and

2. All symbols of the form [pXg], where p and q are states in Q, and X is a stack symbol, in Г.

The productions of G are as follows:

a) For all states p, G has the production 5 [qoZop]. Recall our intuition that a symbol like [goop] is intended to generate all those strings w that cause P to pop Zo from its stack while going from state qo to state p. That is, {qo,w, Zo) h (p, е,б). К so, then these productions say that start symbol S will generate all strings w that cause P to empty its stack, after starting in its initial ID.

b) Let b{q,a,X) contain the pair (r,Y\Y2---Yk), where:

1. a is either a symbol in S or о = e.

2. к can be any number, including 0, in which case the pair is (r, t). Then for all lists of states гьгг,... ,Гй, G has the production

[qXrk] a[rY\ri\[TiY2r2\ [vk-iYhTk]