136 CONTEXT-FREE LANGUAGES
Then, we must have 1 < IyI < 2 (the PDA M’ must read a symbol from the
stack to-operate, and SO@, ~J!E) does not have a successor configuration).
Ify = B E l?U {$}, then the first step must come from an instruction of the
form (r, B) E J’(q, a, A). So, we have, from Case (l), (q, A,p)^3 a(r, B,p).
Also, by the inductive hypothesis, we have (T, B,p) 5 y. Together, we get
(!lAP) 5 aY = x*
Next, if 171 = 2 then y = BA for some B E I’ U {$}, and the first step
comes from an instruction (T, BA) E S’(q, a, A). That is, we have the following
derivation:
(4, x:I A) k (5 Y, BA) p (P, 6 4where x = ay. Then, there must be strings ~1, y2 satisfying yr y2 = y and a
configuration (r’, ~2, A) such that (Y, y, BA) c (r’, ~2, A) < (p, &, E). (The con-
figuration (r’, ~2, A) is the first configuration after (T, y, BA) with the original
stack symbol A in (q,x,A) resurfaced as the top symbol of the stack.) By
Case (2)) we must have the following derivation step in G:
(4, A P) * 45 8 r’> (r’, A, P)*By the inductive hypothesis, we have (T, BJ’) S y1 and (r’A,p) 5 ~2.
Thus, together we have (q, A,p) 5 ayl y2 = x. The above completes the
proof of the correctness of the grammar G.^0
*Example 3.38 Construct a context-free grammar G such that L(G) =
L(M), where Ad is the PDA of Example 3.29.
Solution. First, we transform A4 into M’ with the following 13 instructions:
%I, a, B) = {(cl, AB)),
wL~,B) = -kLBB)),
I a?, E, B) = {(P, B)),
J’(P, 6 $1 = Kf, E)),where s is the new starting state and f is the new unique final state. (For
clarity, we use stack symbols A and B instead of a and b, respectively.)
We now follow the proof of Theorem 3.37 to construct the context-free
grammar G. From the construction, the set V of nontermials of G is V =
{@,C,t) I r,t E {q,p,f},C E {$,A, B}}. However, we observe that many of
these noneterminals are useless, in the sense that the set
{x E c* I (ve) p (Gv))
is empty. We can eliminate these useless nonterminals to simplify the con-
struction: