Problem Solving in Automata, Languages, and Complexity

3.5 Pushdown Automata and Context-Free Grammars 133

by the technique of Example 3.31, using extra temporary states to push extra
symbols into the stack (cf. Exercise 3(b) of Section 3.4).
More precisely, we can define the PDA as M = (Q, C, V U C, 6, s, {q}),
where Q contains s, q and other states to be defined below, and 6 contains the
following instructions:

(2) For every terminal a e C, S(q, a, a) = {(q, E)}.

(3) For every rule ri = (A -+ w1 w2 l l. wk) in R, where each wj, 1 < j < k,

is a single symbol in VUC, we create rE- 1 new states qi,l, qi,2,. 1, qi-&l

and define

J(q,&,A) 3 (qi,l+k),

J(Q i,jJG) = {(!?i,j+h Wk-j)}, for 1 < j^5 k - 2,

s(Qi,k-l,&, E) = { (4, wl)}~

(If k - < 1, i.e., ri = (A -+ WI), where w1 E V U C U {E}, then we define

(4, w) E 4L 6 A)*)

The idea of this construction is quite simple. In particular, the following

two properties are easy to prove by induction on the length of computation

or the length of derivation. We leave the formal proofs to the reader.

(1) Suppose that there is a computation path (q, y, S) p (q, E, y) by M for

someyEC*andyE(VUC)*.Th en, there is a leftmost derivation 5’ + yy

in G.

(2) Suppose S & yy in G, where y E C* and y E (V U c)”. Then, there

L

is a computation path in &! from (q, y, S) to (q, E, 7).

Now, suppose that x E L(M). Then, there is a computation path

(4AS) F (Q,G4* By property (1) above, we have S^2 L x and, hence,

x E L(G). Conversely, if x E L(G) then, by property (a), S (^3) L x implies
(q, x, S) q (q, E,E). Thus, x E L(M).^0
Example 3.36 Consider the context-free grammar G = ({S}, {a, b}, R, S),
with the rules
S + aS 1 aSbS 1 E.
Construct a PDA M such that L(M) = L(G).
Proof. We follow the construction of Theorem 3.35. The resulting PDA M is
as shown in Figure 3.18.
Corresponding to the derivation
S 3 aS a aaSbS 3 aabS 3 aab,