Question

Construct a deterministic finite-state automaton that recognizes the set of all bit strings that contain exactly three 0s.

Short answer

The result is

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

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

Let the start state be \({{\bf{s}}_{\bf{0}}}\).

The \({{\bf{s}}_{\bf{0}}}\) shows that there was no 0’s in the previous digits.

The \({{\bf{s}}_{\bf{1}}}\)has the one 0 in the previous digits.

The \({{\bf{s}}_{\bf{2}}}\)give that there were two 0’s.

The \({{\bf{s}}_{\bf{3}}}\)shows that there were three 0’s.

The \({{\bf{s}}_{\bf{4}}}\) has more than three 0’s.

The \({{\bf{s}}_{\bf{3}}}\) will be the final state. as it is interested in all strings with exactly three 0’s.

As it moves from \({{\bf{s}}_{\bf{0}}}\)to \({{\bf{s}}_{\bf{1}}}\), if it comes across a 0, else It remains at \({{\bf{s}}_{\bf{0}}}\).

It moves from \({{\bf{s}}_{\bf{1}}}\)to\({{\bf{s}}_{\bf{2}}}\), if there is second 0, else It moves back to at\({{\bf{s}}_{\bf{1}}}\),.

It moves from \({{\bf{s}}_{\bf{2}}}\)to\({{\bf{s}}_{\bf{3}}}\), if there is third 0, else It moves back to\({{\bf{s}}_{\bf{2}}}\).

It moves from \({{\bf{s}}_{\bf{3}}}\)to \({{\bf{s}}_{\bf{4}}}\), if there is four 0, else It moves back to\({{\bf{s}}_{\bf{3}}}\).

When it remains at \({{\bf{s}}_{\bf{4}}}\), as the previous bit string will contain more than three 0’s no matter what the next digits are.

Sketch of deterministic finite-state automaton.

The sketch of deterministic finite-state automation can be drawn by five states\({{\bf{s}}_{\bf{0}}}{\bf{,}}{{\bf{s}}_{\bf{1}}}{\bf{,}}{{\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{0}}}\)
\({{\bf{s}}_{\bf{1}}}\)	\({{\bf{s}}_{\bf{2}}}\)	\({{\bf{s}}_{\bf{1}}}\)
\({{\bf{s}}_{\bf{2}}}\)	\({{\bf{s}}_{\bf{3}}}\)	\({{\bf{s}}_{\bf{2}}}\)
\({{\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.