Problem 3 - Finite Automata

Draw a state transition diagram of a deterministic finite automaton with the minimum number of states accepting the regular language represented by the following regular expression. Here, the alphabet is assumed to be $\{0,1\}$.

$$0^{*}1 + 1^{*}0$$

If we denote $\{q_0,q_1,q_7,q_2,q_4,q_8,q_{10}\}$ by $Q_0$, $\{q_2,q_3\}$ by $Q_1$, $\{q_8,q_9\}$ by $Q_2$, $\{q_5,q_6,q_{11}\}$ by $Q_3$, we can deduce from the nondeterministic finite automaton above the deterministic finite automaton with the following transition function:
$\delta(Q_0,0) = [Q_1,Q_3]$
$\delta(Q_0,1) = [Q_2,Q_3]$
$\delta([Q_1,Q_3],0) = Q_1$
$\delta([Q_1,Q_3],1) = Q_3$
$\delta([Q_2,Q_3],0) = Q_3$
$\delta([Q_2,Q_3],1) = Q_2$
$\delta([Q_1, 0]) = Q_1$
$\delta([Q_1, 1]) = Q_3$
$\delta([Q_2, 0]) = Q_3$
$\delta([Q_2, 1]) = Q_2$
Which gives the following deterministic automaton:

$$\includegraphics{epsilon-move-nfa-to-dfa.ps}$$

We look for a minimal deterministic finite automaton. The states 3,4,5 and 0,1,2 are not equivalent between them, since the first bunch consists of final states and the last bunch does not consist of finale states. 1-0 are not equivalent since a 0-input leads them to 1-4 which are not equivalent. The same argument holds for 2-0, 2-1, and 4-5. For 4-3 and 5-3 there are inputs that each time lead them to non-equivalent states. Therefore, they are not equivalent and the deterministic finite automaton found above is minimal.