1.2 Regular Languages 11
(For convenience, we added E to each case. Note that & is in B.)
Now, we can combine cases (1) (a), (4) (6) and use the distributive law
to simplify it into the following regular expression:
(E + O)(lO)‘(E + (o1)* (E + 0) + (oq*(lo)*(E + 1))
= (E + o)(1o)*(o1)*(o + (lo)*@ + 1)).
(Note that E + (Ol)& = (Ol).)
cases (1)’ (3), (5)’ (7) h ave a symmetric form, and set B has the following
regular expression:
(E + q(q*(ol)*(o + (lo)*@ + 1)) + (E + 1)(o1)*(1o)*(1+ (o1)*@ + 0)). 0
Example 1.18 Find a regular expression for the set of all binary strings with
the property that none of its prefixes has two more O’s than l’s nor two more
1 ‘s than 0 ‘s.
Solution. Consider a string x = ~1x2 l l l X~ in the language, where each xi
is a bit 0 or 1. The given property implies that for any positive integer
i < n/2, x2i-1 # x2i. To see this, we assume, for the sake of contradiction,
that there exists a positive integer i < - n/2 such that xzi-1 = x2i. Let i* be
the smallest such i. Without loss of generality, assume xzi+-l = xzi+ = 0.
Then, each pair of x1x2, x3x4,... , ~2i+-3~2;+-2 is either 01 or 10 and, hence,
the prefix ~1x2 l 4 l x2ie- 2 has an equal number of O’s and 1’s. It follows that
the prefix ~1x2 l. .x2+-ix2i+ contains two more O’s than l’s, a contradiction.
Conversely, any string x satisfying that, for all positive integers i < - n/2,
xzi-1 # x2i belongs to this language, since each pair x2iV1x2i is either 10 or
01.
From this characterization, it is now easy to see that this language can be
represented by the regular expression
(01 + 1o)*(o + 1+ E).^0
* Example 1.19 Find a regular expression for the set of al
having no repeated adjace nt symbols over the arabic digits.
1 nonempty strings
SoEution. Let us analyze a general string 20 in the language. It must be of the
form
... g g...g.......
That is, digits 9 separate the string ul into several parts. Each part is a string
over (0, 1,.. ., 8}, having no repeated adjacent symbols. In addition, except
possibly for the first and the last parts, each part is nonempty.
The above analysis suggests us to solve the problem by employing a re-
cursive formula. For k = 0, 1,... , 9, let ak be the kth arabic digit (e.g.,
