394 g Solutions (or Hints) to Chapter-end Exercises
5.17 (a) Let L = {a"b
2/
In > O}. We prove L is not regular by
contradiction. If L is regular, we can apply the pumping lemma. Let
17 be the number of states. Let w = a"b
21 . By pumping lemma,
w = xyz with Ixy I ~ 17, Iy I > 0 and xz E L. As Ixy I ~ 17, xy = am and
y = a
1 where 0 < 1 ~ n. So xz = a"1
b
2
" E L, a contradiction since
17 - 1 :;i= n. Thus L is not regular.
(b) Let L = {d'b
ll1 I 0 < 17 < m}. We show that L is not regular. Let
17 be the number of states and w = a"b
ll1
, where m > n. As in (a),
y = ai, where 0 < 1 ~ n. By pumping lemma xykZ E L for k ~ O. So
a
l
-
l a
1k b'" E L for all k ~ O. For sufficiently large k, 17 - 1 + lk > m.
This is a contradiction. Hence L is not regular.
5.19 Let M = (Q, ~, 8, qo, F) be a DFA accepting a nonempty language.
Then there exists w =ala2 ... a p accepted by M. If p < 17, the result
is true. Suppose p > n. Let 8(qo, ala2 ... a;) = qi for i = L 2, ..., p.
As p > 17, the sequence of states {qj, q2, ..., qp} must have a pair
of repeated states. Take the first pair (qj, qk) (Note % = qk)' Then
8(qo, aja2 ..., aj) = %' 8(%, ai+l
ak) = % and 8(qj' ak+l ...,
a p ) E F. So 8(qo, ala2 ... ajak+l
a p ) = 8(%, aja2 ..., a p ) E F.
Thus we have found a string in ~* whose length is less than p (and
differs from Iwl by k - J). Repeating the process, we get a string of
length m, where m < n.
5.20 Let M =({qo, qIo qj}, {a, b}, 8, qo, {qj}), where qo and qj correspond
to S and A respectively.
Then the NDFA accepting L(G) is defined by Table A5.4.
Table A5.4 Table for Exercise 5.20
SlalelI.
a
b
O(Q2, b) = Ql
D(q4, a) = qj
5.21 The transitions are:
8(qj, a) = q4,
D(qj, b) = q2,
8(q2' a) = q3
8(q3, a) = q2
8(q3' b) = q4
O(q4' b) = q3
Let Aj, A 2 , A 3 , A 4 correspond to qj, q2, Q3, Q4' The induced
productions are Al ~ aA 4 , Al ~ bA 2 , A 2 ~ aA 3 , A 3 ~ aA 2 , A 3 ~