(7.38)
248 ~ Theory of Computer Science
From (7.37) and (7.36). we get (q, tv, Z) pc- (qt, A, A) . By the principle
of induction, (7.27) implies (7.28).
Thus we have proved the auxiliary result. In particular,
[ql), Zo, ql] ::2> 11
iff (ql). 11', ZI) pc- (qt, /\, A)
Now 11' E L(G)
iff 5 :b 1\'
iff S ~ lqo, ZQ. Q'1 :b tv (for some q' by R\)
iff (qQ, W. Zo) pc- (e/, A. A) by the auxiliary result
iff 11' E N(A)
Thus. N(A) = L(G).
Corollary If A is a pda, then there exists a context-free grammar G such that
T(A) = L(G).
Proof By Theorem 7,2 we can find a pda At such that T(A) =N(A'). By
Theorem 7.4 we can construct G such that N(A ' ) =LI G). Thus T(A) =L(G). I
EXAMPLE 7.9
Construct a pda accepting {a"blild' \ m. 11 :2' : I} by null store. Construct the
corresponding context-free grammar accepting the same set.
Solution
The pda A accepting {(/'b
ll1 a
il \m. n :2' : I} is defined as follows:
A = ({qQ. qd, {a. b}, {a, ZQ}, O. qo. ZI). 0)
where 0 is defined by
R 1 : O(ql), a, Zo) = {(qo. aZo) }
R-,: O(qo· a. a) = { (qa. aa)}
R 3 : O(qo. b. a) = {(q l' a)}
R.:,: 6Cql' b. a) = {(qj, a)}
R s : 8(ql' a. a) = {(eil· A)}
R 6 : 8(Q\. A. ZoJ = {(ql, A)}
This is a modification of 8 given in Example 7.2.
We start storing a's until a b occurs (Rules R 1 and R:J. When the current
input symbol is b. the state changes, but no change in PDS occurs (Rule R.,).
Once all the b' s in the input string are exhausted (using Rule R 4 ). the
remaining a's are erased (Rule R s ). Using R(). ZI) is erased. So,
(ql). ai/bll'a", Zo) pc- (ql- A. Zo) r- (qlo A. A)
This means that a"b
lil
(/' E N(A). We can show that
N(A) = {d'b/lla" 1m. n :2' : I}