2. Given the alphabet G = { a, b}. Give the regular expressions for the following languages:

a) all strings with no more that three as

b) all strings with the number of as divisible by three.

c) all strings with exactly one occurrence of the substring aaa

3. Which of the following are true? Explain.

a) baa ? a* b* a* b*

b) (b* a*) ? (a* b*) = a* | b*

c) (a* b*) ? (b* a*) = ?

d) abcd ? (a (cd)* b)*

4. What is the language represented by each of the following regular expressions?

a) ((a* a) b) | b

b) (1 | 01)+

c) 1 (0 |1)* 0

d) (0 | 1)* 011(0 | 1)*

5. Which of the following strings belong to the language described by the regular expression 0*|(0*10*10*10*)*?

a) 1001101 f) 1001001

b) 000 g) 111

c) 110101 h) 11101101

d) 10001000 i) 11000101

e) 011001000111