232 g Theory ofComputer Science
l.e.
(qo· aab. ZoZoZo4J) p:- (qo. A. ~4J)
However. (qo. aab. Zo) r- (qo. abo A); hence the pda cannot make any more
transitions as the PDS is empty. This shows that (7.4) does not imply (7.3)
if we assume a = 4JZo4J. f3 = Zo° Y = ZoZo·
EXAMPLE 7.2
A = ({qo. ql' qt}, {a. b. e}, {a. b. zo}, 8. qo. Zoo {qt})
is a pda. where 8 is defined as
8(q!. a. a) = 8(QI' b. b) = {(qIo A)}
8(QI' A. Zo) = {(Qt' Zo)}
8(CJo· a. Zo) = {(qo. aZo)}.
8(qo•. a. a) = {(qo. aa)},
8(qo. a. b) = {(qo· ab)},
8(qo. e. a) = {(qi. a)},
8(qo. b. Zo) = {(qo· bZrJ)}
8(qo. b. a) = {(qo. bay}
8(qo. b. b) = {(qo. bb)}
8(qo. e. b) = {(qIo b)}, 8(qo. e. Zo)
= {(ql. Zo)}
(7.5)
(7.6)
(7.7)
(7.8)
(7.9)
(7.10)
We can explain 8 as follows:
If A is in initial ill. then using Rule (7.5). A pushes the first symbol of
the input string on PDS if it is a or b. By Rules (7.6) and (7.7). the symbols
of the input string are pushed on PDS until it sees the centre-marker e. By
Rule (7.8). on seeing c. the pda moves to state ql without making any changes
in PDS. By Rule (7.9). the pda erases the topmost symbol if it coincides with
the current input symbol (i.e. if they do not match. the pda halts). By Rule
(7.10). the pda reaches the final state qt only when the input string is
exhausted. and then the PDS has only 4J.
We can explain the concepts of ill. moves. etc. for this pda A. Suppose
the input string is aeab. We will see how the pda processes this string. An
initial configuration is (qo. baeab. 4J). We get the following moves:
(qo· baeab. Zo) r- (qo. aeab. bZ o ) by Rule (7.5)
r- (qo. cab. ab4J)
by Rule (7.7)
r- (q!. abo abZ o )
by Rule (7.8)
r- (qo b. bZ()
by Rule (7.9)
r- (q!. A. Zo)
by Rule (7.10)
r- (qr. A. Z{)
by Rule (7.10)
l.e.