for such manipulations we will not pursue this.
EXERCISES
1. Find all strings in L((a + b) b (a + ab)*) of length less than four.
2. Does the expression ((0 + 1) (0 + 1)*)* 00 (0 + 1)* denote the language in
Example 3.5?
3. Show that r = (1 + 01)* (0 + 1*) also denotes the language in Example 3.6.
Find two other equivalent expressions.
4. Find a regular expression for the set {a n b m : n ≥ 3,m is even}.
5. Find a regular expression for the set {a n b m :( n + m) is even}.
6. Give regular expressions for the following languages.
(a) L 1 = { n b m : n ≥ 4,m ≤ 3}.
(b) L 2 = { n b m : n < 4,m ≤ 3}.
(c) The complement of L 1 .
(d) The complement of L 2 .
7. What languages do the expressions (Ø*)*and aØ denote?
8. Give a simple verbal description of the language L ((aa)* b (aa)* + a (aa)*
ba (aa)*).
9. Give a regular expression for L R , where L is the language in Exercise 1.
10. Give a regular expression for L = {a n b m : n ≥ 1,m ≥ 1,nm ≥ 3}.
11. Find a regular expression for L = {ab n w: n ≥ 3, w ∈ {a, b} + }.
12. Find a regular expression for the complement of the language in Example
3.4.
13. Find a regular expression for L = {vwv: v, w ∈{a, b}*, |v| =2}.
14. Find a regular expression for L = {vwv: v, w ∈{a, b}*, |v|≤3}.