Question

Find a deterministic finite-state automaton that recognizes the same language as the nondeterministic finite-state automaton in Exercise 47.

Short answer

The result is

State	0	1
\({{\bf{s}}_{\bf{0}}}\)	\({{\bf{s}}_{\bf{2}}}\)	\({{\bf{s}}_{\bf{1}}}\)
\({{\bf{s}}_{\bf{1}}}\)	\({{\bf{s}}_{\bf{2}}}\)	\({{\bf{s}}_{\bf{3}}}\)
\({{\bf{s}}_{\bf{2}}}\)	\({{\bf{s}}_{\bf{2}}}\)	\({{\bf{s}}_{\bf{2}}}\)
\({{\bf{s}}_{\bf{3}}}\)	\({{\bf{s}}_{\bf{3}}}\)	\({{\bf{s}}_{\bf{2}}}\)

Step-by-step solution

Construction of deterministic finite-state automaton.

From the exercise (47) I determine the language recognized by the machine is

\({\bf{L(M) = \{ 1\} \{ 0\} *}} \cup {\bf{\{ 0\} \{ 0\} *\{ 1\} \{ 0\} *}}\).

Let us consider four states \({{\bf{s}}_{\bf{0}}}{\bf{,}}{{\bf{s}}_{{\bf{1,}}}}{{\bf{s}}_{\bf{2}}}{\bf{,}}{{\bf{s}}_{\bf{3}}}\).

At state \({{\bf{s}}_{\bf{1}}}\),there is a loop with input 0 and an arrow from\({{\bf{s}}_{\bf{1}}}\) to \({{\bf{s}}_{\bf{2}}}\)with input 0. it can remove the arrow from\({{\bf{s}}_{\bf{1}}}\)to\({{\bf{s}}_{\bf{2}}}\), since \({{\bf{s}}_{\bf{2}}}\)is not a final state and it can never leave \({{\bf{s}}_{\bf{2}}}\)again once you reached it. Thus, the loop with input 0 at \({{\bf{s}}_{\bf{1}}}\) is then sufficient.

At state\({{\bf{s}}_{\bf{3}}}\), there is a loop with input 0 and an arrow from\({{\bf{s}}_{\bf{2}}}\)to\({{\bf{s}}_{\bf{3}}}\) with input 2. It can remove the arrow from\({{\bf{s}}_{\bf{3}}}\)to\({{\bf{s}}_{\bf{2}}}\), since \({{\bf{s}}_{\bf{2}}}\)is not a final state and it can never leave \({{\bf{s}}_{\bf{2}}}\)again once you reached it. Thus, the loop with input 0 at \({{\bf{s}}_{\bf{3}}}\) is then sufficient.

Finally,there are no arrows from state\({{\bf{s}}_{\bf{2}}}\)to another state nor loops at\({{\bf{s}}_{\bf{2}}}\). It can then add loops at \({{\bf{s}}_{\bf{2}}}\)with input 0,1, since \({{\bf{s}}_{\bf{2}}}\)is not a final state.

Sketch of deterministic finite-state automaton.

The sketch of deterministic finite-state automation can be drawn by four states \({{\bf{s}}_{\bf{0}}}{\bf{,}}{{\bf{s}}_{\bf{1}}}{\bf{,}}{{\bf{s}}_{\bf{2}}}{\bf{,}}{{\bf{s}}_{\bf{3}}}\). The sketch is

Other way of representing in tabular form

State	0	1
\({{\bf{s}}_{\bf{0}}}\)	\({{\bf{s}}_{\bf{2}}}\)	\({{\bf{s}}_{\bf{1}}}\)
\({{\bf{s}}_{\bf{1}}}\)	\({{\bf{s}}_{\bf{1}}}\)	\({{\bf{s}}_{\bf{3}}}\)
\({{\bf{s}}_{\bf{2}}}\)	\({{\bf{s}}_{\bf{2}}}\)	\({{\bf{s}}_{\bf{2}}}\)
\({{\bf{s}}_{\bf{3}}}\)	\({{\bf{s}}_{\bf{3}}}\)	\({{\bf{s}}_{\bf{2}}}\)

Therefore, this is the require construction.