Problem Solving in Automata, Languages, and Complexity

2.7 Minimum Deterministic Finite Automata 73

Figure 2.46: Solution to Example 2.51.

Example 2.51 Find the minimum DFA for language (0 + l)*Ol.

Solution. Let us denote this language by L, and study the equivalence classes
of RL. First, we consider the class [E]R~. Note that

[&I RL = {z E (0, I} 1 (VW) [zw E (0 + 1>01 ( w E (0 + l)*ol]}.

Therefore, if II: E [E]&, then x must not end with 0 or 01, for otherwise 31
or X& would be in (0 + l)Ol, which would imply that 1 or E is in (0 + l)Ol.
Conversely, if x does not end with 0 or 01, then it is clearly in [E]R~. So, we
know that [E]& contains strings &, 1 and all strings ending with 11; or,

[&I RL = & + 1 + (0 + 1>*11.

Next, we consider

PI RL = {J: e (011)” 1 (VW) [OW E (0 + l)ol ( EL:W E (0 + l)ol]}.

Since, for w = 1, ow E (0 + l)*ol, we know that x: E [O]R~ must end with 0.

Conversely, it is clear that if x ends with 0, then x E [O]RL. So, we get,

PI RL = (0 + l)*o.

NOW, we note that 1 E [E]R~ and SO [l]~~ = [E]R~; and 00 E [O]RL and so

PO1 RL = PI RL. Therefore, we jump to

WI RL = {x E {0,1) 1 (VW) [OlW E (0 + I)01 e Z’2.U E (0 + l)*ol]}.

By the same argument as that for [O]R~, we can see that [01]~~ contains all
strings x which end with 01; or,

PI RL = (0 + l)*ol.

Finally, we note that [10]~~ = [O]R~, [ll]~~ = [E]RL and, for all strings
zu of length Iw] > 3, w RL x for some x: of length 1x1 < 2. Therefore, there
are only three equivalence classes: [E]R~, [O]R~ and [O1]iL, and the minimum
DFA for L has only three states. We show it in Figure 2.46. Cl