Question

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

Short answer

The result is

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

Step-by-step solution

Construction of deterministic finite-state automaton.

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

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

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

Let start with the state be \({{\bf{s}}_{\bf{0}}}\).Since the empty string in the set S, is not a final state.

If the input starts with a 1, then it remains at state\({{\bf{s}}_{\bf{1}}}\). If the next input is followed by a 0, then it moves on to another non-final state\({{\bf{s}}_{\bf{2}}}\), and if the input contains another 1,then itmoves on to the final state\({{\bf{s}}_{\bf{3}}}\)elseit remains at the non-final state\({{\bf{s}}_{\bf{2}}}\).

If the input starts with a 1, then remains at the state\({{\bf{s}}_{\bf{3}}}\)else it moves on to the non-final state\({{\bf{s}}_{\bf{4}}}\).

If the input starts with a 1, then it moves on to a non-finalstate\({{\bf{s}}_{\bf{4}}}\)and then I never leave at the state \({{\bf{s}}_{\bf{4}}}\)again.

Sketch of deterministic finite-state automaton.

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

Other way of representing in tabular form.

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

Therefore, this is the require construction.