Question 1: Regular Languages [40 pts]

1. Write a regular expression for all strings of as and bs which contains the substring abba.

2. Write a regular expression for all strings of xs and ys where every y is immediately followed by at least 3 xs.

3. Write a regular expression for all strings of ps and qs which contains an odd number of qs.

4. A finite langauge is a language with a finite number of strings. For example, the language with only the string a, ba, and bba is finite, while the langauges in parts 1,2, and 3 above are not finite. Are all finite languages regular? If so, explain why. If not, give an example of a finite langauge which is not regular .