Show that r = (1 + 01) (0+1) also denotes the language in Example 3.6. Find two other equivalent expressions.

6. Show that r = (1 +01)* (0+1*) also denotes the language in Example 3.6. Find two other equivalent expressions. EXAMPLE 3.6 Find a regular expression for the language L = {w E {0, 1}* : w has no pair of consecutive zeros}. Even though this looks similar to Example 3.5, the answer is harder to construct. 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 ... 101 ... 1, that is, the language denoted by the regular expression (1*011*)*. However, the answer is still incomplete, since the strings ending in 0 or consisting of all l's are unaccounted for. After taking care of these special cases we arrive at the answer r = (1*011*)* (0 + 2) + 1* (0 + 2). If we reason slightly differently, we might come up with another answer. If we see L as the repetition of the strings 1 and 01, the shorter expression r= (1 + 01)* (0+2) might be reached. Although the two expressions look different, both answers are correct, as they denote the same language. Generally, there are an unlimited number 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