262 iii Theory ofComputer Science
Solution
We define a pda 1\1 as follows:
lvi = ({Cfo, qd· {a. b}. {a. b. ZoL O. qo, Zo, {qd)
where 0 is defined by
O(q(), a, Zo) = {(qi. Zo)}
O(qo, b. Zo) = {(qo, bZ o )}
O(qo, a, b) = {(qo. A)}
O(qo, b, b) = {(qo. bb)}
O(CfI' a, Zo) = {(ql' aZo)}
O(Cfj. h. Zo) = {(qo. aZo)}
O(Cfj, a. a) = {(Cfl, aa)}
O(CfI' b, a) = {(Cfj, A)}
(7.53)
(7.54)
(7.55)
(7.56)
(7.57)
(7.58)
(7.59)
(7.60)
The construction can be explained as follows:
If the pda M is in the final state qj, it means it has seen more a's than
b·s. On seeing the first a. lvi changes state (from qo to ql) «7.53». Afterwards
it stores the a' s in PDS without changing state (7.57) and (7.59». It stores
the initial b in PDS ((7.54» and also the subsequent b's «(7.56». The pda
cancels a in the input string, with the first (topmost) b in PDS «(7.55». If all
b's are matched with stored a's, and M sees the bottom of PDS, M moves
from Cfj to Cfo ((7.58»). The b's in the input string are cancelled on seeing a
in the PDS (7.60»).
Ai is deterministic since 0 is not defined for input A. The reader is advised
to check that Cft is reached on seeing an input string h' in L
EXAMPLE 7.17
Construct a pda M accepting L = {c/hi(J Ii = j or j = k} by final state.
Solution
We define pda M as follows:
I'vi = ({qo. Cfj, ...• Cfd, {a, b, C}. {Z{), X}. 0, Cfo, 20, {Cfj, q3})
where 0 is given by
O(Cfo. A, Zo)= {(Cf], Z{). (Cf2· L{j). (Cf3, Zo)}
o(qj. c. 20)= {(Cf], Zo)}
0(Cf2' a. Zo) = {(Cf2' XZ o )}
0(Q2, a. X) = t(Q2, XX)}
O(q2, b, X) = (q)" b. X) = {(Cf)" A)}
O(q),. A. Zo) = {(Cf], Zo)}
(7.61)
(7.62)
(7.63)
(7.64)
(7.65)
(7.66)