PDA by (Grammar )

Figure 6.S: Organization of construction.s showing equivalence of three ways of defining the CFLs

6.3.1 From Grammars to Pushdown Automata

Given a CFG G. we construct a PD.A that simulates the leftmost derivations of G. Any left-sentential form that is not a terminal string can be written as xAa, where A is the left,most variable, x is whatever terminals appear to its left, and a is the string of terminals and variables that appear to the right of .4,

a) Convert P to another PDA P] that accepts by empty stack r.he same language that P accepts by final state; i.e., N{Pi) - L(P).

b) Find a PDA Pa sncii that ЦР2) = N(P)\ i.e., P2 accepts by final state what P accepts by empty stack.

! Exercise 6.2.7: Show that if P is a PDA, then there is a PDA P2 with only two stack symbols, such that L{P2) = L{P). Hint: Binary-code the stack alphabet of P.

*! Exercise 6.2.8: A PDA is called restricted if on any transition it can increaic the height of the stack by at most one symbol. That is, for any rule 6[q,a. Z) contains {p.. 7), it mnst be that I7I < 2. Show that if P is a PDA, then there is a restricted PDA P3 such that L{P) = ЦРл).

6.3 Equivalence of PDAs and CFGs

Now, we shall demonstrates that the languages df;fined by PDAs are exactly the context-free languages. The plan of attack is suggested by Fig. 6.8. The goal is to prove that the foUowing three classes of languages:

1. The context,-free languages, i.e., the languages defined by CFG s.

2. The languages that are accepted by final state by some PDA.

3. The languages that are accepted by empty stack by some PD.4.

are all the same claws. We have already shown that (2) and (3) are the same. It turns out to be easiest next to show that (1) and (3) are the same;, thus Lniplying the e<iuivalence of all three.

We call Aa the tail of this left-sentential form. If a left-sentential form consists of terminals only, then its tail is e.

The idea behind the construction of a PDA from a grammar is to have the PDA simulate the sequence of left-sentential forms that the grammar uses to generate a given terminal string w. The tail of each sentential form xAa appears on the stack, with A at the top. At that time, x will be represented by our having consumed x from the input, leaving whatever of w follows its prefix X. That is, if w = xy, then у will remain on the input.

Suppose the PDA is in an ID {q,y,Aa}, representing left-sentential form xAa. It guesses the production to use to expand A, say A -> /3. The move of the PD.A is to replace A on the top of the stack by у5, entering ID {q,y,a). Note that there is only one state, q, for this PDA,

Now {q,y,8a) may not be a representation of the next left-sentential form, because h may have a prefix of terminals. In fact, .3 may have no variables at all, and q may have a prefix of terminals. Whatever terminals appear at the beginning of fla need to be removed, to expose the next variable at the top of the stack. These terminals are compared against the next input symbols, to make sure our guesses at the leftmost derivation of input string w are correct; if not; this branch of the PDA dies.

If we succeed in this way to guess a leftmost derivation of ш, then we shall eventually reach the left-sentential form w. At that point, all the symbols on the stack have either been expanded {if they are variables) or matched against the input (if they are terminals). The stack is empty, and we accept by empty stack.

The above informal construction can be made precise as follows. Let G = {V,T, Q, S) be a CFG. Construct the PD.A P that accepts L(G) by empty stack as follows:

Pi{qlT,VvT,S,q,S) where transition function 5 is defined by:

1. For each variable A,

6{q, €, A) = {(q,&) I A -> is a production of G}

2, For each terminal a, S{g,a,a) - {{q,E)).

Example 6.12: Let us convert the expression grammar of Fig. 5.2 to a PDA, Ret:all this grammar is:

I a\b\Ia\Ib\IO\Il

E I\ E*E \ Е + Е\{Е)

The set of termmals for the PDA is {a,i, 0,1, (,), H-, These eight symbols and the symbols / and E form the stack alphabet. The transition function for the PDA is:

a) 6{g,eJ) = {{q,a), [qja], {q,Ib), [qJO), {qjl)}.

b) S{q,t,E) = {{q,I), {q,E + E), {д,Е*Е), {q,(E))}.

c) <5(g,o,a) = {(g,e)}; S{q,b,b) = %,0,0) = {{д,е)У, 5{q,l,l) = {{q,e)y, 5{q,i,0 = {(ff,)}; 5(9.),)) = {(9.)}; = {(g,e)}; й(д,*,*) = {(5,е)}.

Note that (a) and (b) come from rule (1), while the eight transitions of (c) come from rule (2), Also, 6 is empty except as defined by (a) through (c). □

Theorem 6.13: If PDA P is constructed from CFG G by the construction above, then NiP) = L{G).

PROOF: We shall prove that vj is in N{P) if and only if w is in L{G). (If) Suppose w is in L{G). Then w has a leftmost derivation 5 = 7, => 7a => 7 - uj

Irfi hn im

We show by induction on i that {q,w,S) (g, J/i) t)i where t/i and Qj are a representation of the left-sentential form 7;. That is, let a.i be the tail of 7, and let 7i - Xiat- Then yi is that string such that xiyi ~ w: i.e., it is what remains when xi is removed from the input.

BASIS: For г - 1, 7i = 5. Thus, Xi - and j/i - w. Since {q, w, S) (q, ш, S) by 0 moves, the basis is proved.

INDUCTION: Now we consider the case of the second and subsequent left-sentential forms. We assume

{q,w,S) iq,yi,ai)

and prove (g,u;, S) f {q, у;+\, ai+i). Since a; is a tail, it begins with a variable A. Moreover, the step of the derivation 7; 7;+i involves replacing A by one of its production bodies, say в. Rule (1) of the construction of P lets us replace .4 at the top of the stack by 8, and rule (2) then allows us to match any terminals on top of the stack with the next input symbols. As a result, we гекЬ the ID (q,yi-i-iTCii+i), which represents the next left-sentential form 7;ц-1.

To complete the proof, we note that = e, since the tail of 7 (which is w) is empty. Thus, {q,w,S) (д,е,б), which proves that P accepts w by empty stack.

(Only-if) We need to prove something more general: that if P executes a sequence of moves that has the net effect of popping a variable A from the top of its stack, without ever going below A on the stack, then A derives, in G, whatever input string was consumed from the input during this process. Precisely:

Ii{q,x,A) (g,f, fi), then A x. The proof is an induction on the number of move.s taken by P.