Solutions (or Hints) to Chapter-end Exercises &,;l, 389
4.17 Let the given granm1ar be G j . The production A ~ xB where
x = ala2 ... all is replaced by A ~ alAj, Al ~ a2A 2, ..., An-I ~
allB. The production A ~ y, where y = b l b 2 ... b m is replaced by
A ~ bjB], B j ~ b 2 B 2 , ••• , B/1/-1 ~ b/1/' The grammar G 2 whose
productions are the new productions is regular and equivalent to G j .
Chapter 5
5.1 (a) 0 + 1 + 2
(b) 1(11)*
(c) w in the given set has only one a which can occur anywhere in
w. So w =xay, where x and y consist of some b's (or none).
Hence the given set is represented by b* ab*.
(d) Here we have three cases: w contains no a, one a or two a's.
Arguing as in (c), the required regular expression is
b* + b* ab* + b* ab* ab*
(e) aa(aaa)*
(0 (aa)* + (aaa)* + aaaaa
(g) a(a + b)* a
5.2 (a) The strings of length at most 4 in (ab + a)* are A, a, ab, aa,
aab, aba, abab, a:;, aaba, aaab and d+. The strings in aa + bare
aa and b. Concatenating (i) strings of length at most 3 from the
first set and aa and (ii) strings of length 4 and b, we get the
required strings. They are aa, aaa, abaa, aaaa, aabaa, abaaa,
as, ababb, aabab, aaabb, and aaaab.
(c) The strings in (ab + a) + (ab + a)2 are a, ab, aa, abab, aab and
aha. The strings of length 5 or less in (ab + a)3 are a
3 , abaa,
aaab, ababa. The strings of length 5 or less in (ab + a)4 are a
4 ,
a
3 ab, aba
3 • In (ab + a)5, as is the only string of length 5 or less.
The strings in a* are in (ab + a)* as well. Hence the required
strings are A, a, ab, a 2 , abab, aab, aba, a
3 , abaa, aaab, ababa,
a
4 , aaaab, abaaa, and as.
5.3 (a) The set of all strings starting with a and ending in abo
(b) The strings are either strings of a's followed by one b or strings
of b's followed by one a.
(c) The set of all strings of the form vw where a's occur in pairs in
v and b's occur in pairs in w.
5.5 The transition system equivalent to (ab + a)*(aa + b) (5.2(a» is
given in Fig. AS.l.
4.17 Let the given granm1ar be G j . The production A ~ xB where
x = ala2 ... all is replaced by A ~ alAj, Al ~ a2A 2, ..., An-I ~
allB. The production A ~ y, where y = b l b 2 ... b m is replaced by
A ~ bjB], B j ~ b 2 B 2 , ••• , B/1/-1 ~ b/1/' The grammar G 2 whose
productions are the new productions is regular and equivalent to G j .
Chapter 5
5.1 (a) 0 + 1 + 2
(b) 1(11)*
(c) w in the given set has only one a which can occur anywhere in
w. So w =xay, where x and y consist of some b's (or none).
Hence the given set is represented by b* ab*.
(d) Here we have three cases: w contains no a, one a or two a's.
Arguing as in (c), the required regular expression is
b* + b* ab* + b* ab* ab*
(e) aa(aaa)*
(0 (aa)* + (aaa)* + aaaaa
(g) a(a + b)* a
5.2 (a) The strings of length at most 4 in (ab + a)* are A, a, ab, aa,
aab, aba, abab, a:;, aaba, aaab and d+. The strings in aa + bare
aa and b. Concatenating (i) strings of length at most 3 from the
first set and aa and (ii) strings of length 4 and b, we get the
required strings. They are aa, aaa, abaa, aaaa, aabaa, abaaa,
as, ababb, aabab, aaabb, and aaaab.
(c) The strings in (ab + a) + (ab + a)2 are a, ab, aa, abab, aab and
aha. The strings of length 5 or less in (ab + a)3 are a
3 , abaa,
aaab, ababa. The strings of length 5 or less in (ab + a)4 are a
4 ,
a
3 ab, aba
3 • In (ab + a)5, as is the only string of length 5 or less.
The strings in a* are in (ab + a)* as well. Hence the required
strings are A, a, ab, a 2 , abab, aab, aba, a
3 , abaa, aaab, ababa,
a
4 , aaaab, abaaa, and as.
5.3 (a) The set of all strings starting with a and ending in abo
(b) The strings are either strings of a's followed by one b or strings
of b's followed by one a.
(c) The set of all strings of the form vw where a's occur in pairs in
v and b's occur in pairs in w.
5.5 The transition system equivalent to (ab + a)*(aa + b) (5.2(a» is
given in Fig. AS.l.