Question

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

Short answer

The result is

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

Step-by-step solution

Construction of deterministic finite-state automaton.

From the exercise (46) it determines the language recognized by the machine is

\({\bf{L(M) = \{ 100,101\} *}} \cup {\bf{\{ 1\} \{ 001,011\} *}}\).

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

Let’s start with the state be \({{\bf{s}}_{\bf{0}}}\) there is no arrow with input 0. it then creates a non-final state\({{\bf{s}}_{\bf{3}}}\), in whichitsends the input 0 towards. Once itarrives at\({{\bf{s}}_{\bf{3}}}\),it will never leave the state again.

At state\({{\bf{s}}_{\bf{1}}}\), there is no arrow with input 1. Itdraws the arrow with input 1 from \({{\bf{s}}_{\bf{1}}}\)to the non-final state\({{\bf{s}}_{\bf{3}}}\), such that none of these strings will be recognized.

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{3}}}\)	\({{\bf{s}}_{\bf{1}}}\)
\({{\bf{s}}_{\bf{1}}}\)	\({{\bf{s}}_{\bf{2}}}\)	\({{\bf{s}}_{\bf{3}}}\)
\({{\bf{s}}_{\bf{2}}}\)	\({{\bf{s}}_{\bf{0}}}\)	\({{\bf{s}}_{\bf{0}}}\)
\({{\bf{s}}_{\bf{3}}}\)	\({{\bf{s}}_{\bf{3}}}\)	\({{\bf{s}}_{\bf{3}}}\)

Therefore, this is the require construction.