a now start state p and an accepting state r. We shall use Xo as the bottom-of stack marker. Pj, is formally defined:

Pf = {{p,q,r},{i,e},{Z,Xo},6F,p,XoAr}) where Sp consists of:

1. Sf{p, e, Xq) = {{q, 2X0)}. This rule starts Pf simulating Рдг, with Xq as a bottom-of-stack-marker.

2. 6г{ч,г, Z) = {(q,ZZ)}. This rule pushes a Z when we see an г; it simulates Piv-

3. 5F{q,e,Z) - {(qe)}. This rule pops a Z when we see an e; it also sinmlates Pn .

4. (5f(<?, e, Xo) = {(r, 6, e)}. That is, Pp accepts when the simulated Pjm would have emptied its stack.

□

6.2.4 PVom Final State to Empty Stack

Now, let us go in the opposite direction: take a PDA Pp that accepts a language L by final state and construct another PDA Pv that accepts L by empty stack. The construction is simple and is suggested in Fig. 6.7. Prom each accepting state of Pp, add a transition on e to a new state p. When in state p, Pn pops its stack and does not consume any input. Thus, whenever Pp enters an accepting state after consuming input w, Pjv will empty its stack after consuming w.

To avoid simulating a situation where Pp accidentally empties its stack without accepting, P must also use a marker Xq on the bottom of its stack. The marker is Рл-з start symbol, and like the construction of Theorem 6.9, Рдг must start in a new state po, whose sole function is to push the start symbol of Pp on the stack and go to the start state of Pf- The construction is sketched in Fig. 6.7, and we give it formally in the next theorem.

Figure 6.7: Pn simulates Pp and empties its stack when and only when Рдг enters an accepting state

Theorem 6.11: Let L be ЦРр) for some PDA Pf = (Q, S, Г,,до, o, P). Then there is a PDA Pjv such that L = N{Pn).

PROOF: The construction is as suggested in Fig. 6.7. Let

Pn = (q и {po,p},i:,T и {Xo}..Sn,Po,Xo) where is defined by:

1. Sipo, е,Хо) = {{qo, ZoXq)}. We start by pusliing the start symbol of Pf onto the stack and going to the start state of Pp-

2. For all states q in q, input symbols я in S or a = e, and У in Г, Slq, a. Y) contains every pair that is in Sf(q,a, Y). That is, P simulates Py.

3. For all accepting states q in F and stack symbols У in Г or У = Xq, /v(g, e,У) contains (p.e). By this rule, whenever Pp accepts, P can start emptying its stack without consuming any more input.

4. For all stack symbols У in Г or У = Хц. Лл(р,б,У) = {{p,t)}. Once in state Pi which only occurs when Pp has accepted, P pops ev(>ry symbol on its stack, until the stack is empty. No further input is consumed.

Now, we must prove that w is in N{Pn) if and only if w is in L(Pp). The ideas are similar to the proof for Theorem 6.9. The if part is a direct simulation, and the only-if part requires that we examine the limited number of things that the constructed PD.\ P can do.

(If) Suppose iqo,w, Zq) {q,c,a) for some accepting state q and stack string

a. Using the fact that every transition of Pp is a move of P/v, and invoking Theorem 6.5 to allow us to keep Xq below the symbols of Г on the stack, we know that (qo,w,ZoXo) (q,€,aXo). Then Fjv can do the follov-ing:

(Pq,w,Xo)\- {qo,w,ZDXD) {q,e,aXo) (p,e,e)

Pn Pn P

The fir.st move is by rule (1) of the construction of P/v, while the last sequence of moves is by rules (3) and (4). Thus, w is accepted by P, by empty .stack.

(Only-if) The only way P can empty its stack is by entering stat<; p, since Xq is sitting at the bottom of stack and Xq is not a symbol on which Pp has any moves. The only way p/v can enter state p is if the simulated Pp enters an accepting state. The first move of P is surely the move given in rule (1). Thus, every accepting computation of P/v looks like

{ро,,Ха)\- (9o,w,ZoXo) i; (g,e,QXo) (p,e,e) P.\ Pn Pn

where q is an accepting state of Pp.

Moreover, between IDs {qQ,w,Z{)XQ) and {q,€,otXo), all the moves are moves of Pp. In particular, Xq was never the top stack symbol prior to reaching ID {q,e,QXQ). Thus, we conclude that the same computation can occur in Pp. without the Xo on the stack; that is, (qo.w, Zq) (?, б,о). .Now we see that

Pp accepts w by final state, so w is in L{Pp). □

* Although a could be c, in which case Pp has emptied its stack at the same time it accepts.

6.2.5 Exercises for Section 6.2

Exercise 6.2.1: Design a PDA to accept each of tlie following languages. You may accept cither by final state or by empty stack, whichever is more convenient.

* a) {0 1 I n > 1).

b) The set of all strings of Os and Is such that no prefix has more Is than Os.

c) The set of ;ill strings of Os and 1 s with an equal mimber of Os and Is. ! Exercise 6.2.2: Design a PDA to accept each of the following languages.

* a) (ttfrc* \ i - j or j - k}. Note that this language is different from that

of Exercise 5.1.1(b).

b) The set of all strings with twice as many Os as Is. !! Exercise 6.2.3: Design a PD.A to accept each of the following languages.

a) {аЫс I i / j or i 7 k}.

b) The set of all strings of as and bs that are not of the form ww, that is, not equal to any string repeated.

*! Exercise 6.2.4: Let P be a PDA with empty-stack language L N{P), and suppose that e is not in L. Describe how you would modify P so that it accepts L и {e} by empty stack.

Exercise 6.2.5: PDA P = {{go,qi,(l2,QsJ}.,{a;b],{Zo,A,B}J,qo,Zo,{f}) has the following rules defining 6:

<(фь a, Zq) = ((?i, AAZo) 5(?o, b, Zo) = {q-2,BZo) s{qQ, e, Zq) = (/, e)

6{qi,a,A) = (f/i, AAA) Siqi,b,A) = (9 e) 6{qi, e, Zo) = (90, Zo)

Siq2,a,B) = {q3,f) 6{q2,b, B) = (q-i, BB) s(q2,e, Zu) = {qa, Zo)

6(q3,€,B) = (ga,e) 5{q:i,€,Zo) = ($i,AZo)

Note that, since each of the sets above has only one choice of move, we have omitted the set brackets from each of the rules.

* a) Give an execution trace (sequence of IDs) showing that string bab is in

L{P).

b) Give an execution trace showing that abb is in L{P).

c) Give the contents of the stack after P has read ba from its input. ! d) Informally describe L{P)-

Exercise 6.2.6: Consider the PDA P from Exercise 6.1.1.