Chapter 5: Regular Sets and Regular Grammars ~ 171
Solution
(a) b*ab*ab*
(b) (a + b)*a(a + b)*a(a + b)*
(c) b*ab*ab* + b*ab*
(d) (a + b)*aa(a + b)*
EXAMPLE 5.28
Find a regular expression consisting of all strings over {a, b} starting with any
number of a's, followed by one or more b's, followed by one or more a's,
followed by a single b, followed by any number of a's, followed by band
ending in any string of a's and b's.
Solution
The Le. is a*b b*a a*b(a + b)*.
EXAMPLE 5.29
Find the regular expression representing the set of all strings of the form
(a) d"b
ii d'
where In, n, p :2 1
(b) d"bc-l c3p
where 111, n, p :2 1
(c) a"bac-"'bcwhere 111 :2 O. n :2 1
Solution
(a) aa*bb*cc*
(b) aa*(bb)(bb)*ccc(ccc)*
(c) aa*b(aa)*bb
EXAM PLE 5.30
Find the sets represented by the following regular expressions.
(a) (a + b)*(aa + bb + ab + ba)*
(b) (aa)* + (aaa)*
(c) (1 + 01 + 001)*(1\ + 0 + 00)
(d) a + b(a + b)*
Solution
(a) The set of all strings having an odd number of symbols from {a, b}*
(b) {x E {a}* I Ix I is divisible by 2 or 3}
(c) The set of all strings over {a, I} having no substring of more than
two adjacent O·s.
(d) {a. b, ba, bb, baa, bab, bba. bbb, ... }