404 g Solutions (or Hints) to Chapter-end Exercises
sentential form. By considering leftmost derivations, we can show that
the number of variables in a is ::; mn. (Use the fact that G/ is in GNF).
Define:
G l = (Vf:, ~, PI, 5) where
Vf: = {[a]llal ::; mn and a E Vn
51 = [51]
PI = {[Af3] ~ b[a 13] IA ~ ba is in P, 13 E Vf: and laf3l ::; mn}
G I is regular. It can be verified that L(G I ) = L(G').
Chapter 7
7.1 (qo, aacaa, Zo) t- (qo, acaa, aZo) r- (qo, caa, aaZo) r- (qj, a, aaZo)
r- (qjo a, aZo) r- (qj, A, Zo) r- (qj' A, Zo)·
(i) Yes, the final ill is (qr, A, Zo)·
(ii) Yes, the final ill is (qjo A, aZo)·
(iii) No, the pda halts at (ql' ba, aZo)·
(iv) Yes, the final ill is (ql' A, abaZo)
(v) Yes, the final ill is (qo, A, babaZo)·
7.2
(i) (qj, A, aZo).
(ii) Halts at (q), b. A).
(iii) (qo, A, a
5
Zo)·
(iv) Does not move.
(v) Does not move.
(vi) Halts at (qjo ab, Zo).
7.3 (a) Example 7.9.
(b) The required pda A is defined as follows:
A = ({qo, ql' q:;}, {a, b}, {a, Zo}, 6, qo, Zo, 0). 6 is defined by
6(qo, a, Zo) = {(ql' aZo)} , 6(ql' a, a) = {(qlo aa)}
6(qlo b, a) = {(q:;, a)},
6(q:;, b, a) = {(qj, A)}
6(q\, A, Zo) = {(qjo A)}.
(c) A = ({qo, qd, {a, b, C}, {Zo, Zd, 6, qo, Zo, 0)
6 is defined by
6(qo, a, Zo) = {(qo, ZIZa)},
6(qo, a, ZI) = {(qo, ZIZ 1)}
6(qo, b, Z\) = {(qj, A)},
6(ql' b, ZI) = {(qlo A)}
6(qlo c, Zo) = {(ql, Za)},
6(ql' A, Zo) = {(ql' A)}
Note that on reading a, we add ZI; on reading b we remove ZI and
the state is changed. If the input is completely read and the stack
symbol is Zo, then it is removed by a A-move.
7.4 (a) Example 7.9 gives a pda accepting {a"b
lll a" 1m, n ~ I} by null
store. Using Theorem 7.1, a pda B accepting the given language by
final state is constructed.