This production says that one way to pop X and go from state q to state rk is to read a (which may be e), then use some input to pop Yi off the stack while going from state r to state ri, then read some more input that pops I2 off the stack and goes from state ti to гз, and so on.

We shall now prove that the informal interpretation of the variables [qXp] is correct:

[qXp] w if and only if (q, w, X) (p, e, e).

(If) Suppose {q,w,X) P (p,e, e). We shall show [qXp] w Ъу induction on the number of moves made by the PDA,

BASIS: One step. Then (p,e) must be in 5(g,iu,X), and w is either a single symbol or c. By the construction of G, [qXp] - ш is a production, so [qXp] => w.

INDUCTION: Suppose the sequence {q,w,X) 1 (p, e,e) takes n steps, and n > 1. The first move must look Ике

{q,w,X)h{ro,x,Y,Y2---Yk) (p,e,e)

where w = ax for some a that is either e or a symbol in S. It follows that the pair (го, YiY2---Yk) must be in d{q, a,X). Further, by the construction of G, there is a production [qXrk] -> a[rQYiri][TiY2r2] [rk-iYkrk], where:

! Tjfc = p, and

2, ri, Г2,. .,Гк-i are any states in Q.

In particular, we may observe, as was suggested in Fig. 6.10, that each of the symbols Yi,Y2,...,Yk gets popped off the stack in turn, and we may choose Pi to be the state of the PDA when Yi is popped, for г = 1,2,..., A: - 1. Let X = W1W2 - Wk, where Wi is the input consumed while Yi is popped off the stack. Then we know that (r, i,Wi,y;) 1 (rj,£,e).

As none of these sequences of moves can take as many as n moves, the inductive hypothesis applies to them. We conclude that [ri-iyin] Wi. We may put these derivations together with the first production used to conclude:

[qXrk] => a[roYiri][riYir2] [гк-iYkrk] awi[г1У2Г2][г2Гзгз] [гк-iYkrk] аш1Ш2[г2УзГз] [гк-iYkrk]

where Гк = p.

(Only-if) The proof is an induction on the number of steps in the derivation.

BASIS: One step. Then [qXp] w must be a production. The only way for this production to exist is if there is a transition of P in which X is popped and state q becomes state p. That is, (p,e) must be in 6{q,a,X), and a = w. But then {q,w,X) h (p,e,e).

INDUCTION: Suppose [qXp] w Ъу n steps, where n> 1. Consider the first sentential form explicitly, which must look like

[qXrk] о[гоУ1П][п ¥2Г2] [Tk-lYkTk] w

where rjt - p. This production must come from the fact that (roYiV - Yk) is in S{q, a,X).

We can break w into w = awiW2---Wk such that [г 1К;п] wi for all г - 1,2,..., ft. By the inductive hypothesis, we know that for all г,

{ri-i,Wi,Yi) (г;,е,б)

If we use Theorem 6,5 to put the correct strings beyond Wi on the input and below Yj on the stack, we also know that

{ri-i,WiWi+i Wk,YiYi+i---Yk) {ri,Wi+i Wk,Yi-, -Yk)

If we put all these sequences together, we see that

{q,awiW2---wi;,X) h {го,Ш1Ш2 ш, У1У2 Уй) {ri,W2W3---wk,Y2Y3---Yk) {r2,vJ3---Wk,Y3---Yk) (Гй,е,е)

Since Гк - p. we have shown that {q,w,X) (p,e,e).

We complete the proof as follows, S w if and only if [ooP] for some p, because of the waj the rules for start symbol S are constructed. We just proved that [qoZop] ш if and only if (qWfZo) h (p,e,e), i.e., if and only if P accepts X by empty stack. Thus, L{G) = N{P). □

Example 6.15: Let us convert the PDA Рдг - {{q}, {г,е}, {Z}, 5,Ч, Z) from Example 6.10 to a grammar. Recall that Pn accepts all strings that violate, for the first time, the rule that every e (else) must correspond to some preceding г (if). Since Pn has only one state and one stack symbol, the construction is particularly simple. There are only two variables in the grammar G:

a) 5, the start symbol, which is in every grammar constructed by the method of Theorem 6,14, and

b) \qZq\, the only triple that can be assembled from the states and stack symbols of Pn-

The productions of grammar G are as follows:

1. Thfi only production for 5 is 5 [qZq]. However, if there were n states of the PDA, then there would be n productions of this type, since the last state could be any of the n states. The first state would have to be the start state, and the stack symbol wtudd have to be the start symbol, as in our production above.

2. From the fact that 5ni{q,i,Z) contains {q,ZZ), we get the production [qZq\ i[qZq][qZq]. Again, for this simple example, there is only one production. However, if there were n states, then this one rule would produce productions, since the middle two states of the body could be any one state p, and the last states of the head and body could also be any one state. That is, if p and г were any two states of the PDA, then production [qZp] i[qZr\[rZp] would be produced.

3. From the fact that {-[q.e.Z) contains (Q,e), we have production

[qZq] с

Notice that in this case, the list of stack symbols by which Z is replaced is empty, so the only symbol in the body is the input symbol that caused the move.

We may, for convenience, replace the triple {qZq\ by some less complex symbol, say A. If we do, then the complete grammar consists of the productions:

A lAA \ e

In fact, if we notice that A and 5 derive exactly the same strings, we may identify them as one, and write the complete grammar as

G = {{S},{i,e),{SiSS I e},5)

□

6.3.3 Exercises for Section 6.3 * Exercise 6.3.1: Convert the grammar

S OSl I A A -> lAO I 5 I f

to a PDA that accepts the same language by empty stack.

Exercise 6.3.2: Convert the grammar

S aAA

A aS \bS \a