Question

4) (9 pts) Give regular expressions for the following languages on (la, b) a) L1 = { w : na(w) mod 3 = 1). b) L2w w ends in aa) c) L3 = all strings containing no more than three a's.

Answer 1

a) The regular expression for L1 = {w : na(w} mod 3 = 1}

na(w} mod 3 = 1 means that the number of a's can be 1, 4, 7, .... (3*n+1). Regular expression for this is a(aaa)*.

Hence, the overall regular expression is: (b*ab*(aaa)*b*)* (ans).

b) The regular expression for L2 = {w : w ends in aa} is given as:

(a*b*)*aa (ans)

c) The regular expression for L3 = all strings contaning no more than three a's:

b*(a + λ)b*(a + λ)b*(a + λ)b* (ans)