Question

Construct a deterministic finite-state automaton that recognizes the set of all bit strings that contain at least 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{3}}}\)	\({{\bf{s}}_{\bf{3}}}\)

Step-by-step solution

Construction of deterministic finite-state automaton.

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

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

Now \({{\bf{s}}_{\bf{0}}}\)shows that there were no 0’s in the previous digit.

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

The state \({{\bf{s}}_{\bf{2}}}\)give that there were two 0’s in the previous digits.

The state \({{\bf{s}}_{\bf{3}}}\)shows that the string contains at least three 0’s in the previous digits.

The state \({{\bf{s}}_{\bf{3}}}\)will be final state and contains at least three 0’s.

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 a second 0, else It move back to \({{\bf{s}}_{\bf{1}}}\).

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

Once I arrived at \({{\bf{s}}_{\bf{3}}}\), I will remain there, as the previous bit string still contain at least 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 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{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{3}}}\)	\({{\bf{s}}_{\bf{3}}}\)

Therefore, this is the require construction.