Question

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

Short answer

The result is:

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

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

\({{\bf{s}}_{\bf{0}}}\)shows that the last two digits were 0.

\({{\bf{s}}_{\bf{1}}}\)has the last two digits was 00.

\({{\bf{s}}_{\bf{2}}}\)give that the last two digits were 00.

\({{\bf{s}}_{\bf{3}}}\)shows that the string contains 000.

\({{\bf{s}}_{\bf{0}}}{\bf{,}}{{\bf{s}}_{\bf{1}}}\)and \({{\bf{s}}_{\bf{2}}}\)all are in the final state. As I will make sure that all strings containing three consecutive zero ends at state\({{\bf{s}}_{\bf{3}}}\).

I move from \({{\bf{s}}_{\bf{0}}}\)to\({{\bf{s}}_{\bf{1}}}\), if I come across a 0, else I remain at\({{\bf{s}}_{\bf{0}}}\).

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

I move from \({{\bf{s}}_{\bf{2}}}\)to\({{\bf{s}}_{\bf{3}}}\), if there is a third 0, else I move back to\({{\bf{s}}_{\bf{0}}}\). Once I arrived at\({{\bf{s}}_{\bf{3}}}\), I will remain there.

Sketch of deterministic finite-state automaton.

Another way of representing in tabular form.

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

Therefore, this is the required construction.