by Rules (7.5)-(7.7)
by Rule (7.8)
by Rule (7.9)
by Rule (7.10)
234 ~ Theory of Computer Science
Solution
Consider the pda given in Example 7.2. Let yVC1V
T E L. Write w =ala2 ... a",
where each ai is either a or b. Then, we have
(qo· ata2 ... a"cw
T Zo)
~ (qo. cw
T
• a ll a ll _l
~ (qt· a,,czn-l ... aI- a,,czl/-I ... (ltZo)
~ (ql' A. Zo)
r- (qf' A. Zo)
Therefore, wcw
T E T(A) , i.e. L ~ T(A).
To prove the reverse inclusion, it is enough to show that L' ~ T(Ar. Let
x E V'.
Case 1 x does not have the symbol c. In this case the pda never makes a
transition to ql' So the pda cannot make a transition to qf as we cannot apply
Rule (7.10). Thus. x E T(A)'.
Case 2
(qo, WICl1/2' 20)
~ (qo, CW2· wtZo)
r- (qt, W2· wrZo)
As W2 1:- wr the pda cannot reach an ill of the form (qj, A, Zo). So we
cannot apply (7.10). Therefore. x E TCA)'.
Thus we have proved V' ~ T(Ar.
The next definition describes the second type of acceptance.
Definition 7.7 Let A = (Q, L, r. 8. qo. Zo, F) be a pda. The set N(A)
accepted by null store (or empty store) is defined by
N(A) = {w E L*1(qo, lV, 20) ~ (q, A, A) for some q E Q}
In other words, y1/ is in N(A) if A is in initial ill (qo, w, 20) and empties
the PDS after processing all the symbols of Y\'. SO in defining N(A) , we
consider the change brought about on PDS by application of w, and not the
transition of states.
EXAMPLE 7.4
Consider the pda A given by Example 7.2 with an additional rule:
8(qf' A. Zo) = {(qt; A)}
Then.
N(A) = {wcwTlw E {a. b}*}
(7.11)