Example 6.8: The PDA P of Example 6.2 петег empties its stack, .so N{P) = 0. Howewr, a small modification will allow P to accept Lu.u,r by empty stack as well as by final state. Instead of the transition S{qi,e, Zq) - {(q2, Zq)}, use d(Qi,E,Zo) = {{q2,f.)}. Now, P pops the last symbol off its stack as it a<;cepts, and L{P) = N(P) = L r- □

Since the set of accepting states is irrelevant, we shall sometimes leave oi? the last (seventh) component from the specification of a PDA P, if all we care about is the language that P accepts by empty stack. Thus, we would write P as a six-tuple {Q, S, Г, S, qo, Zq).

6.2.3 From Empty Stack to Final State

We shall show that the classes of languages that are L{P) for some PDA P is the same as the class of languages that are N{P) for some PDA P. This class is also exactly the context-free languages, as we shall see in Section 6.3. Our first construction shows how to take a PDA P that accepts a language L by empty stack and construct a PDA Pr that accepts L by final state.

Theorem 6.9: U L = N{Piv) for some PDA Рл = (Q-. K,r,(Siv,go,Z(,), then there is a PDA Pp such that L = LiPp).

PROOF: The idea behind the proof is in Fig. 6.4. We use a new symbol Xo, which must not be a symbol of Г; Xq is both the start symbol of Pp and a marker on the bottom of the stack that lets us know when Pjv has reached an empty stack. That is, if Pp sees Ao on top of its stack, then it knows that PjV would empty its stack on the same input.

Start

Figure 6.4: Pf simulates Р\ and accepts if Pv empties its stack

We also need a new start state, po, whose sole function is to push Z( the start symbol of P, onto the top of the stack and enter state Qq, the start

state of Рл- Then, Pp simulates Pn, until the stack of P is empty, which Pp detects because it sees Ao on the top of the stack. Finally, we need another new state, p/, which is the accepting state of Pf; this PDA transfers to state pf whenever it discovers that Рдг would have emptied its stack. Tlie specification of Pp is as follows:

Pr = (0 и {po,pj},i:SU {Xa},6F,Po,Xo,{Pl}) where is defined by:

1. rff (pG,e, Ao) = {{oZoXo)}. In its start state, Pf makes a spontaneous transition to the start state of Psv, pushing its start symbol Zo onto the stack.

2. For all states q in Q, inputs a in S or a = e, and stack symbols Y in Г, 5i.-{q,a,Y) contains all the pairs in 5дг(д,а,У).

3. In addition to rule (2), {g, £,Xo) contains (p/, e) for every state q in Q.

We must show that w is in L{Pp) if and only if w is in iV{Pjv).

(If) We are given that (o, uj, Zo) (9,e,e) for some state q. Theorem 6.5 lets

us insert Ao at the bottom of the stack and conclude (50, w, ZoXo) I- {q, c, Xo).

Since by rule (2) above, Pp has all the moves of Рдг, we may also conclude that {qQ,w, ZoXo) r (g, e, Ao). If we put this sequence of moves together with the

initial and final moves from rules (1) and (3) above, we get:

{pQ,w,Xo)y- {qo,w,ZoXo) (?,c,Xo)l- (p/,e,e) (6.1)

Pf Pf Pi.-

Thus, Pf accepts w by final state.

(Only-if) The converse requires only that we observe the additional transitions of rules (1) and (3) give us very hmited ways to accept w by final state. We must use rule (3) at the last step, and we can only use that rule if the stack of Pf contains only Xo- No Aos ever appear on the stack except at the bottommost position. FVirther, rule (1) is only used at the first step, and it must be used at the first step.

Thus, any computation of Pp that accepts w must look like sequence (6.1). Moreover, the middle of the computation - all but the first and last steps - must also be a computation of Pfv with Xo below the stack. The reason is that, except for the first and last steps, Pp cannot use any transition that is not also a transition of Рл, and Xo cannot be exposed or the computation would end at the next step. We conclude that {qo,w, Zq) }r (g,e,e). That is, w is in JV(PAr).

Example 6.10: Let us design a PDA tliat processes sequences of ifs and elses in a С program, where i stands for if and e stands for else. Recall from Section 5.3.1 that there is a problem whenever the number of elses in any prefix exceeds the nnmber of ifs, because then we cannot match each else against its previous if. Thus, we shall use a stack symbol Z to count the difference between the number of is seen so far and the number of rs. This simple, one-state PDA, is suggested by the transition diagram of Fig, 6,5.

Start

Figure 6.5: A PDA that accepts the if/else errors by empty stack

We shall push another Z whenever we see an i and pop a Z whenever we se<; an e. Since we start with one Z on the stack, we actually follow the rule that if the stack is Z , then there have been n - 1 more is than es. In particular, if the stack is empty, than we have seen one more e than г, and the input read so far has just become illegal for the first time. It is these strings that our PDA accepts by empty stack. The formal specification of P is:

Fn = {{q]Ai.e.},{Z}.,SN:Q,Z)

where Sn is defined by:

1. (5jv(q,i>Z) - {{q.ZZ)}. This rule pushes a Z when we sec an i.

2, dN{Q,e,Z) = {(g,e)}. This rule pops a Z when we see an e.

Start

Figure 6.6: Construction of a PDA accepting by final state from the PDA of Fig. 6.5

Now, let us construct from P\ a PDA Pp that accepts the same language by final state; the transition diagram for Py is shown in Fig. 6.6. We introduce

Do not be coiicorned that we are using new staf.r.s p and т lierc, while thti construction in Theorem (5.9 used po and pj. Names of states are arbitrary, of course.