74 FINITE AUTOMATA
Example 2.52 Construct the minimum DFA for language (0 + l)*O(O + 1)“.
Solution. This language L contains all strings UI of length at least 10 whose
tenth rightmost bit is 0. We will show that RL defines the following set of
equivalence classes:
First, we show that all equivalence classes in Q are distinct. Since, for any
x with 1x1 < - 9, 09-i21 4 L and Ox09-1”1 E L, the strings E and Ox are not
in the same equivalence class. Now, we look at Ox and Oy with x # y. We
consider three cases:
Case 1. 1x1 < lyl. Since Ox09+l 9 L and Oy09-lYl E L, strings Ox and Oy
are not in the same equivalence class.
Case 2. 1x1 > lyl. Symmetric to Case 1.
Case 3. 1x1 = IyI. We can write x = xlx2~-*x~fl, and y = yly2+*yk for
some Ic > 1, where each xi and each yj is a bit in (0, l}. Since x # y, there
exists an-integer i, 1 < - i < Ic, - such that xi # yi. Without loss of generality,
assume that xi = 0 and yi = 1. In this case, OXO~-~+~ E L and Oy09-k+i 4 L.
Thus, Ox and Oy are not in the same equivalence class.
Next, we show that every binary string is in one of the equivalence classes
in Q. For each string w E (0 + l) , consider its suffix u of length min( IzuI, 10).
First, if u E l, then we observe that uly E L for some y E (0, 1)’ if and
only if Iy] > -^10 and the tenth rightmost bit of y is 0. (If 1yI < 10, then either
lu)yl < 10 or the tenth rightmost bit of ‘wy is a bit in u and, hence, equal to
1.) It follows that for any string y E (0, l}, ‘wy E L if and only if y E L,
and so w RLE. Next, if u = 1jOx for some j > 0 and x E {O,l}* then, by
following the same argument as above, we can &e that ‘wy E L if and only if
Oxy E L. Thus, wRLOx.
Now, we can use the above analysis to construct the minimum DFA M =
(Q, (0, l}, 4 [E]RL, F) for L, where Q is the set defined above,
and the transition function 6 can be described as follows:
(1) d([&]Rt,O) = [O]Rm ~([+,I 1) = [&]RL+
(2) If 1x1 < 9 th en, for a E (0, 1), b([Ox]RL7a) = [oxa]RLe
(3) If x = l9 then h([ox]~~,O) = [O]RLl S([O&, I>= [E]R~.
(4) If 1x1 = 9 and x = liOy for some y, with 0 < i < 8, - - then S([OX]R~, a) =
[Oya]R,, for a E {o,l). clFrom the above example, we can see that the minimum DFA for language
(0 + l)‘O(O + 1),-l must contain 2” states. However, it is easy to construct
an NFA for the same language with n + 1 states. Thus, the exponential
size increase of the subset construction is unavoidable in these cases. It also