(2) For each instruction (p, BA ) E d’(q, a, A), where IBI = 1 and a E ~U{E},
we define the rules, T’) (T’, A, r), for all r, r’ E Q u {f}-
3.5 Pushdown Automata and Context-Free Grammars 135
Each nonterminal (q, A, p) will generate the following set:
Ix E c* I (4, &A) t-* (P,V))*To do so, we define the following rules of G:
(1) For each instruction (p, B) E S’(q, a, A), where IBI = 1 and a E C U {E},
we define the rules(wb) --)a(~,&$ forallr~Qu(f).
(3) For each instruction (p, E) E S’(q, a, A), where a E CU {E}, we define the
rule
(cl, 4 P> + a*To see that the above construction works correctly, it suffices to show that
(q,A,p) 3 x if and only if (q,e,A) C (P,E,E)
(so that (s, $, f) 3 x if and only if (s, x, $) P (f, q E)).
We first prove the forward direction by induction on the length of the
derivation (q, A, p) > x. First, if this derivation is of length 1. Then, it must
use a rule created in Case (3) b a ove, and it follows that (q, x, A) t- (p, E,F).
Next, assume that (q, A,p) 2 1x3 has length > 2. Then, the first step of the
derivation may come from a rule created in Cise (1) or in Case (2).
In Case (1) (q,A,p) 3 a(r, B,p) > ay = x, for some state r E Q U
{f}. By the inductive hypothesis, we have (r, y, B) p (p, &, E). Thus, by the
condition of (1) (q, x4) k (TY,B) p (PA+
In Case (2) (q, A,p) 3 a(r, B, 7”) (T’, A,p) 3 ay = x, for some states
r,r’ E Q u {f}. Th en, we have (r, B, r’) > ~1, (r’, A,p) $ y2 for some
y1 and y2 satisfying yly2 = y. By the inductive hypothesis, we know that
(r, ~1, B) < (r’, E, E) and (r’, ~2, A) < (p, q E). By the condition of (a), we have
(cvY,A) I- (‘,Y,BA) c om b ining them together, we have a computation as
follows:
(4, aYlY2, A) t- (5 YlY2, BA) c (A Y2, A) c (P,V)*
Thus, we have proved the forward direction.
For the backward direction, we assume that (q, x, A) c (p, E, E) in n moves.
Suppose n = 1. Then, we must have an instruction (p,~) E J’(q, a, A) and
X = a E C U {E}. So, by Case (3), (q,A,p) > a = x. Now, for n > 1, we
assume that (q, x, A) I- (r, y, y) p (~,E,E), where x = ay for some a E CU {E}.