Example 3.3
For Σ = {a,b}, the expression
r=(a+b)*(a+bb)
is regular. It denotes the language
L (r)= {a, bb, aa, abb, ba, bbb,…}.
We can see this by considering the various parts of r. The first part, (a + b)*,
stands for any string of a’s and b’s. The second part, (a + bb) represents either an
a or a double b. Consequently, L(r) is the set of all strings on {a, b}, terminated
by either an a or a bb.
Example 3.4
The expression
r =(aa)* (bb)* b
denotes the set of all strings with an even number of a’s followed by an odd
number of b’s; that is,
L (r) = {a 2n b 2m+1 : n ≥ 0, m ≥ 0}
Going from an informal description or set notation to a regular expression
tends to be a little harder.
Example 3.5
For Σ = {0, 1}, give a regular expression r such that
L(r) = {w ∈ Σ*: w has at least one pair of consecutive zeros}.
One can arrive at an answer by reasoning something like this: Every string in L (
r) must contain 00 somewhere, but what comes before and what goes after is