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

* Exercise 6.3.3: Convert the PDA P = {{p,g},{0,1},{A ,Zo},(S,g, Zo) to a CFG, if 5 is given by:

1. 5iqA,Za) = {{q,XZo)}.

2. 5iq,l,X) = {{q,XX)}.

3. S{q,0,X) = {{p,X)}.

4. S{q,e,X) = {iq,e)}.

5. 5Cp,l,X) = {(p,e)}.

6. 6(p,0,Zo) = {{g,Zo)}.

Exercise 6.3.4: Convert the PDA of Exercise 6.1.1 to a context-free grammar.

Exercise 6.3.5: Below are some context-free languages. For each, devise a PDA that accepts the language by empty stack. You may, if you wish, first construct a grammar for the language, and then convert to a PDA.

a) {a b c2f + ) I n > 0, m > 0}.

b) {afrJc* I г = 2j or J = 2k}. ! c) {О ! I n < m < 2n}.

*! Exercise 6.3-6: Show that if P is a PDA, then there is a one-state PDA Pi such that N{Pi) = N{P).

! Exercise 6.3.7: Suppose we have a PDA with s states, t stack symbols, and no rule in which a replacement stack string has length greater than u. Give a tight upper bound on the number of variables in the CFG that we construct for this PDA by the method of Section 6.3.2.

6.4 Deterministic Pushdown Automata

While PDAs are by definition allowed to be nondeterministic, the deterministic subcase is quite important. In particular, parsers generally behave like deterministic PDAs, so the class of languages that can be accepted by these automata is interesting for the insights it gives us into what constructs are suitable for use in programming languages. In this section, we shall define deterministic PDAs and investigate some of the things they can and cannot do.

6.4.2 Regular Languages and Deterministic PDAs

The DPDAs accept a class of languages that is between the regular languages and the CFLs. We shall first prove that the DPDA languages include all the regular language.s.

Theorem 6.17: If Lis a regular language, then L = L{P) for some DPDA P.

6.4.1 Definition of a Deterministic PDA

Intuitively, a PDA is deterministic if there is never a choice of move in any situation. These choices are of two kinds. I£ 6(q, a,X] contains more than one pmr, then surely the PDA is nondeterministic because we can choose among these pairs when deciding on the next move. However, even if S{q, a, X) is always a singleton, we could still have a choice between using a real input symbol, or making a move on e. Thus, we define a PDA P - ((3,S!,r,J, qiOjZcF) to be deterministic (a deterministic PDA or DPDA), if and only if the following conditions are met:

1. 6{q,a,X) has at most one member for any g in Q, о in E or a = e, and X in Г,

2. If 5{q,a,X) is nonempty, for some a in E, then 5{q,e>X) must be empty.

Example 6.16 : It turns out that the language Lbjr oi Example 6.2 is a CFL that has no DPDA. However, by putting a center-marker с in the middle, we can make the language recognizable by a DPDA. That is, we can recognize the language icwr = {vjcw ш is in (0 -f-1)*} by a deterministic PDA.

The strategy of the DPDA is to store Os and Is on its stack, until it sees the center marker c. it then goes to another state, in which it matches input symbols against stack symbols and pops the stack if they match. If it ever finds a nonmatch, it dies; its input cannot be of the form wcw. If it succeeds in popping its stack down to the initial symbol, which marks the bottom of the stack, then it accepts its input.

The idea is very much like the PDA that we saw in Fig. 6.2. However, that PDA is nondeterministic, because in state q it always has the choice of pushing the next input symbol onto the stack or making a transition on e to state qi; i.e., it has to guess when it has reached the middle. The DPDA for shown as a transition diagram in Fig. 6.11.

This PDA is clearly deterministic. It never has a choice of move in the same state, using the same input and stack symbol. As for choices between using a real input symbol or e, the only e-transition it makes is from qi to q2 with Zq at the top of the stack. However, in state qj, there are no other moves when Zq is at the stack top. □

с , Zq /Zq £ , Zq /Z q

c, 0/ 0

с , 1 / 1

Figure 6.11: A delerniuiistic PDA accepting L-mcwr

PROOF: Essentially, a DPDA can simulate a deterministic finite automaton. The PDA keeps some stack symbol Zo on its stack, because a PDA has to have a stack, but really the FDA ignores its stack and just uses its state. Formally, let A = (0,Е,5л,Со,Р) be a DFA. Construct DPDA

P = {0,S,{Zo},5p,№,Zo,F)

by defining ep{q,a,Zo) = {(p, Zo)} for all states p and q in Q, such that 6л{д,а)р.

We claim that {qo,w, Zo) H (p, e, Zq) if and only if л(о,гу) - p. That is,

P simulates A using its state. The proofs in both directions are easy inductions on and we leave them for the reader to complete. Since both A and P accept by entering one of the states of F, we conclude that their languages are the same. □

Ji we want the DPDA to accept by empty stack, then we find that our language-recognizing capability is rather limited. Say that a language L has the prefix property if there are no two different strings x and у m L such that X is a prefix of y.

Example 6.18: The language icr of Example 6.16 has the prefix property. That is, it is not possible for there to be two struigs wcw and xcx, one of which is a prefix of the other, unless they are the same string. To see why, suppose vjcw is a prefix of xcx, and w Ф x. Then m must be shorter than X. Therefore, the с in wcw comes in a position where xcx has a 0 or 1; it is a position in the first x. That point contradicts the assumption that wcw is a prefix of xcx.

On the other hand, there are some very simple languages that do not have the prefix property. Consider {O}*, i.e., the set of all strings of Os. Clearly,

0, Zq/OZq

1, Zq/IZo 0, 0/0 0

0 , 1/0 1

1,0/10 0 , 0/ e

1,1/11 1 , 1 / £