Question

Write down the regular expressions for the following set of strings over {a, b}:

1.Strings that contain no more than one occurrence of the string aa.

2.All strings containing aba:

3.All strings of odd length

4.A string in this language must have at least two a's.

5.All strings that begin with a, and have an even number of b

Bonus - All strings with “a” at every odd position

Answer 1

1.Strings that contain no more than one occurrence of the string aa.
(b*+(ab)*) aa (b*+(ba)*)

2.All strings containing aba:
(a+b)*(aba)(a+b)*

3.All strings of odd length
   (a+b)[(a+b)(a+b)]*

4.A string in this language must have at least two a's.
(a+b)*a(a+b)*a(a+b)*

5.All strings that begin with a, and have an even number of b
    a(a*ba*ba*)*