3.5 Pushdown Automata and Context-Free Grammars 137
(1) We observe that the PDA M cannot move from p to q, nor from f to
p OF q. Therefore, we can eliminate all nonterminals (p, C, q), (f, c, p),
(f, C, q) for all C E {$, A, B).
(2) Since there is no action at state f, we can eliminate all nonterminals
(f, c, f) for c E ($9 A, B)
(3) We observe that the stack symbol $ is never used until we want to move
to state f. Therefore, we can eliminate all nonterminals (Y, $, t) for
0 e {%P)
(4) When we move to f, we must remove the stack symbol $. So, the
nonterminals (7’, C, f) are useless for Y E {q,p} and C E {A, B}.
(5) We never pop up anything from the stack in state q. Therefore, (4, A, q)
and (q, B, q) are useless.
After these eliminations, there are only six nonterminals left:
v = {(q, $7 f>, (P, $9 f), (!A, P>, (!l, B, P), (PAP), (P, 4 P>),where (q, $, f) is the starting symbol.
Now, for each instruction of M’ (except S’(s, E, E) = {(q, $)}), we con-
struct corresponding grammar rules for G. For instance, from instruction
w?, a, $> = NLA$)), we get the following rule:
(a, $7 f> + a (CL A, P> (P, $4 f),and from the instruction S’(q, b, A) = {(q, BA)}, we get
(CL 4 P) + b (41 BY P) (P, A, P>*The complete grammar G is as follows:
(4, $, f) + (P, $7 f> I a (a, 4 P> (P, $Y f> I b (!L BY P> (PY $, f>J
(a, A, P) + (P, 4 P) I a (CL 4 P> (PJ 4 P> I b kl,BY P) (P7 4 P>,
(q,B,p) + (PAP) I a(!LA,P)(PJ4P) I kB~P)(PJ%P)>
(PAP) -+ a, (P,B,P) + b, (P, $, f) + &*For
path:
instance, M’ accepts the inupt abba with the follow ing computation
(s, abba, E) I- (q, abba, $) I- (q, bba, A$) I- (q, ba, BA$) k (p, ba, BA$)
k (P, a, A$) I- (P, &, $) t- (f, 6 +The corresponding leftmost derivation of abba by G is as follows:
(4Af) * a(cLA,P)(P,$,f) * ab(q,B,p)(p,A,p)(p,$,f)
* ab (P, BY P> (P, A P) (P, $, f > * abb (P, 4 P) (P, $> f >
* abba (p, $, f) =+ abba. Cl