Question

1. Write the regular expression for the following sets (4.5)

4.1 All strings over {a,b} that are odd in length

4.2 All strings over {a,b} whose length is not a multiple of 3

4.3 All strings over a,b that start with aa and end with bb

Answer 1

1)
((a+b)(a+b))*(a+b)

2)
((a+b)(a+b)(a+b))*((a+b) + ((a+b)(a+b)))

3)
aa(a+b)*bb

Explanation:
-------------
(a+b) matches a single letter a or b.
(a+b)(a+b) matches two letters (aa, ab, ba, or bb)
((a+b)(a+b))* matches even number of letters
so, ((a+b)(a+b))*(a+b) matches odd number of letters

((a+b)(a+b)(a+b))* matches letters of multiple of 3
and then ((a+b) + ((a+b)(a+b))) matches either 1 or two letters to make it match any string with length of not a multiple of 3.