134 CONTEXT-FREELANGUAGES
Figure 3.18: PDA for Example 3.36the accepting computation path of PDA M is
(5 aab, E) I- (CL aab, S) I- (Ql,l, aah S) k (4, aah as> t- (41 ah s>
t- (q2,1d, s> t- (a 2,29 ab, bS) I- (42,3, ab, SbS) I- (!I, 4 asq
I- (q, b, SbS) t- (!I, OS) t- (a7 5 S) I- (47 5 El* cl- Theorem 3.37 For every PDA M, there is a context-free grammar G such
that L(G) = L(M).
Proof. Let M = (Q, C, I’, 4 4, F) b e a PDA. First, we modify it to an equiva-
lent PDA M’ which always looks at the top symbol of the stack at each move
(except the very first move). To do so, we need to make two adjustments on
our PDA model:
(a) We push, at the first move, a special symbol $ into the stack to indicate
the bottom of the stack. This prevents the possible stack underflow problem.
(b) We allow the new PDA M’ to push two stack symbols into the stack
at one move. This is necessary in order to push a new symbol into the stack.
It is easy to see that this change does not increase the computational power
of the PDA ( see Exercise 3(c) of Section 3.4).
More precisely, we define a new PDA M’ = (Q U (~1, f}, C, IT U {$}, S’, ~1,
{f}), where s1 and f are two new states, $ is a new stack symbol, and S’
contains the following instructions:
(1) ~‘(Sl,~,E) = {(s,$))*
(2) S’(q,E,$) = {(f,~)}, for all q E F.
(3) (P, B) E wL a, A), if (P, B) E s(4, a,A), where A E I’ and B E I? U {E}.
(4) (P, BA) E QL a,A) for all A E I? U {$}, if (p, B) E S(q, a,& where
B E r u {E}.
It is clear that L(M’) = L(M).
Now, we construct a context-free grammar G to simulate the computation
of M’. Grammar G contains the following nonterminal symbols:
V = {(qAp) I q,p E Qu {f},A E ru {$))-