Chapter 7: Pushdown Automata 1;\ 263
0(q3' a. ZO) = {(q3' Zo)}
0(Q3' b. Zo) = {(q). XZ o )}
0«(1). h. X) = {(q). XX)}
O(q). c, X) = O(qc,. c. X) = {(qc" A)}
o(C]c" A. Zo) = {«(/3. A)}
(7.67)
(7.68)
(7.69)
(7.70)
(7.71)
The states qb q:. C]~ stand for aObOc k , dbic k , dbic i respectively where
i > 0, j ;:: O. k ;:: O. (7.61) indicates the initial guess. The three choices
correspond to the three cases.
(q(i. c'. 2 0 ) = (qo. Ac
k • Zo) ~ (qlo c'. Zo) 1- (q], A, Zo)
by (7.61) and (7.62). As ql is a final state. c
k E TUvf).
The pda in state q: will not change state and stores a's in the input string
as X's in PDS «(7.63) and (7,64). On seeing the first b after many a·s. M
changes its state to qJ, and cancels X in PDS for subsequent b's «7.64)). If
it reaches the bottom of PDS. M goes back to ql. which is an accepting state
«(7.76)). So Iv! accepts db
i • It continuous to be in state q! on seeing c's
subsequently «7.62). So. Ai accepts a'bic'.
For dealing with aibic i . Ai makes the initial guess using (7.61) and reaches
state qo. It simply reads a's without changing state or PDS «7.67».
!vI subsequently replaces b with X and changes to state q). Afterwards M
goes on changing b's to Xs «7.69). On seeing a c, !vI changes state.
Subsequent c's are matched with X's (which correspond to b's read earlier)
and X's in PDS are cancelled. On reaching the bottom of PDS, M reaches q3.
a final state «7.71)).
Thus. aOhOc
k • (/l/c
k , aibic
i E TUYf) for i > O. j ;:: O. k ;:: O. Hence.
T(!vf) = L.
EXAMPLE 7.18
Convert the graJ1lJ11ar 5 -+ aSb! A. A -+ bSa I5 IA to a pda that accepts the
same language by empty stack.
Solution
We construct a pda A as
A = ({q}. {a. b}. {So A. a. b}. o. q, 5.0)
where 0 is defined by the following rules
o(q. A. 5) = {(q. aSb). (q. A)}
o(q. A. A) = {(q, bSA). (q. S). (q. A)}
O(q. a. a) = {(q, A)}
o(q. b. b) = {(C]. A)}
and A is the required pda.
0(q3' a. ZO) = {(q3' Zo)}
0(Q3' b. Zo) = {(q). XZ o )}
0«(1). h. X) = {(q). XX)}
O(q). c, X) = O(qc,. c. X) = {(qc" A)}
o(C]c" A. Zo) = {«(/3. A)}
(7.67)
(7.68)
(7.69)
(7.70)
(7.71)
The states qb q:. C]~ stand for aObOc k , dbic k , dbic i respectively where
i > 0, j ;:: O. k ;:: O. (7.61) indicates the initial guess. The three choices
correspond to the three cases.
(q(i. c'. 2 0 ) = (qo. Ac
k • Zo) ~ (qlo c'. Zo) 1- (q], A, Zo)
by (7.61) and (7.62). As ql is a final state. c
k E TUvf).
The pda in state q: will not change state and stores a's in the input string
as X's in PDS «(7.63) and (7,64). On seeing the first b after many a·s. M
changes its state to qJ, and cancels X in PDS for subsequent b's «7.64)). If
it reaches the bottom of PDS. M goes back to ql. which is an accepting state
«(7.76)). So Iv! accepts db
i • It continuous to be in state q! on seeing c's
subsequently «7.62). So. Ai accepts a'bic'.
For dealing with aibic i . Ai makes the initial guess using (7.61) and reaches
state qo. It simply reads a's without changing state or PDS «7.67».
!vI subsequently replaces b with X and changes to state q). Afterwards M
goes on changing b's to Xs «7.69). On seeing a c, !vI changes state.
Subsequent c's are matched with X's (which correspond to b's read earlier)
and X's in PDS are cancelled. On reaching the bottom of PDS, M reaches q3.
a final state «7.71)).
Thus. aOhOc
k • (/l/c
k , aibic
i E TUYf) for i > O. j ;:: O. k ;:: O. Hence.
T(!vf) = L.
EXAMPLE 7.18
Convert the graJ1lJ11ar 5 -+ aSb! A. A -+ bSa I5 IA to a pda that accepts the
same language by empty stack.
Solution
We construct a pda A as
A = ({q}. {a. b}. {So A. a. b}. o. q, 5.0)
where 0 is defined by the following rules
o(q. A. 5) = {(q. aSb). (q. A)}
o(q. A. A) = {(q, bSA). (q. S). (q. A)}
O(q. a. a) = {(q, A)}
o(q. b. b) = {(C]. A)}
and A is the required pda.