242 g Theory of Computer Science
(q, 010
4 , S)
r- (q, 010
4 , OBB)
r- (q, 10
4
, BB)
r- (q, 10
4
, ISB)
r- (q, 0
4 , SB)
r- (q, 0
4
, OBBB)
r- (q, 0
3 , BBB)
f-2- (q, 0
3 , 000)
f-2- (q, A, A)
Thus.
by Rule R[
by Rule R 3
by Rule R 2 since (q, IS) E a(q, A, B)
by Rule R 4
by Rule R[
by Rule R 3
by Rule R: since (q, 0) E a(q, A, B)
by Rule R 3
010
4 (;;; N(A)
Note: After entering (q. 10 4 . BB), the pda may halt for a different sequence
of moves, for example, (q, 10
4 , BB) r- (q, 10
4 , OB) r- (q, 10
4
, 00). As
6(q, 1, 0) is the empty set, the pda halts.
Let us continue with the proof of the theorem.
Step 2 (Proof of the construction, i.e. L(G) = N(A)). First we prove L(G)
(;;; N(A). Let W E L(G). Then it can be derived by a leftmost derivation. Any
sentential form in a leftmost delivation is of the form f.1Aa, where U E L*,
A E V N and a E (V N u L)*. We prove the following auxiliary result: If
S ~ uAa by a leftmost derivation, then
(q, UV. S) f-2- (q. v, Aa) for every v E L*
(7.22)
We prove (7.22) by induction on the number of steps in the derivation of
uAa. If S b uA, then u =A, a =A, and S =A. As (q, v, S) f-2- (q, v, S), there
is basis for induction.
Suppose S ~ uAa by a leftmost derivation. This derivation can be split
11
as S => u[A[a[ ~ uAa. If the A[-production we apply in the last step is
A[ ---'} u:Aa:, then u = UjU::> a = a:aj'
n
As S => u [A j a j , by induction hypothesis,
(q, UjU:V, S) f-2- (q, U:V, Ajaj)
(7.23)
As Ai ---'} II:Aa: is a production in P, by Rule Rj we get (q, A, A j ) r(q, A, U2Aa:). Applying Results 1 and 2 in Section 7.1, we get
(q, U2V, A[ at) r- (q, U:V. u2Aa: a [)
Hence,
(7.24)