completely arbitrary. An arbitrary string on {0,1} can be denoted by (0+1)*.
Putting these observations together, we arrive at the solution
r= (0 + 1)* 00(0 + 1)*.
Example 3.6
Find a regular expression for the language
L = {w∈{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 1’s are unaccounted for. After taking care of these
special cases we arrive at the answer
r= (1*011*)* (0 + λ) + 1* (0 + λ)
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 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
r= (1+01)* (0 + λ)
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 expressions.
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
Putting these observations together, we arrive at the solution
r= (0 + 1)* 00(0 + 1)*.
Example 3.6
Find a regular expression for the language
L = {w∈{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 1’s are unaccounted for. After taking care of these
special cases we arrive at the answer
r= (1*011*)* (0 + λ) + 1* (0 + λ)
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 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
r= (1+01)* (0 + λ)
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 expressions.
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