Question

Use the procedure you described in Exercise 39 and the finite-state automaton you constructed in Exercise 29 to find a deterministic finite-state automaton that recognizes the set of all bit strings that do not contain three consecutive 1s.

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

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

The state \({{\bf{s}}_{\bf{1}}}\) shows the last digit was 1.

The state \({{\bf{s}}_{\bf{2}}}\) has the last two digits were 11.

The state \({{\bf{s}}_{\bf{3}}}\) gives that the string contained 111.

It moves from \({{\bf{s}}_{\bf{0}}}\)to \({{\bf{s}}_{\bf{1}}}\), if it comes to cross a 1, else it will remain at\({{\bf{s}}_{\bf{0}}}\).

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

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

Once it arrived at \({{\bf{s}}_{\bf{3}}}\), it will remain there.

In the exercise (41) the determine the bit string containing consecutive three 1’s.\({{\bf{s}}_{\bf{3}}}\) was the only final state. In this exercise to determine the bit string not containing consecutive 1’s. I then require that \({{\bf{s}}_{\bf{3}}}\)is not a final state, but \({{\bf{s}}_{\bf{0}}}{\bf{,}}{{\bf{s}}_{\bf{1}}}\)and\({{\bf{s}}_{\bf{2}}}\) are final state.

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

Therefore, this is the require construction.