3.1 REGULAR EXPRESSIONS 75 Even though this looks similar to Example 3.5, the answer is harder to One helpful observation is that whenever a 0 occurs, it must be followed immediately by a 1. Such a substring may be preceded and followed by an arbitrary number of 1's. This suggests that the answer involves the repetition of strings of the form 1... that is, the language denoted by the regular However, the answer is sti incomplete, since the strings ending in o or consisting of all I's are unaccounted for. After taking care of these special cases we arrive at the answer r 011') (o A) 1 (0+ A). If we reason slightly differently, we might come up with another answer. If we see Las the repetition of the strings 1 and 01, the shorter expression (1 01) (0 A) might be reached. Although the two expressions look different, both answers are correct, as they denote the same language. Generally, there are an unlimited mamber of regular expressions for any given language. Note that this language is the complement of the language in Example 3.5. However, the regular expressions are not very similar and do not suggest clearly the close relationship between the languages. The last example introduces the notion of equivalence of regular ex- pressions. We say the two regular expressions are equivalent if they denote the same language. One can derive a variety of rules for simplifying regular expressions (see Exercise 20 in the following exercise section), but since we have little need for such manipulations we will not pursue this. EXERCISES Find all strings in L (a 6) (a ab) of length less than four. ample 3.5? 3. Show that r +01) (0+ 1 also denotes the language in Example 36. Find two other equivalent expressions. Find a regular expression for the set fa n 3 m is even). a. Find a regular expression for the set (a"b" (n m) is even) 6. Give regular expressions for the following languages. 4, m s 3)