Question

Construct a deterministic finite-state automaton that recognizes the set of all bit strings that contain the string 101.

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

Step-by-step solution

Construction of deterministic finite-state automaton.

Let \({\bf{S = \{ 0,1\} *\{ 101\} \{ 0,1\} *}}\)

Let's start state be \({{\bf{s}}_{\bf{0}}}\). Since the empty string is not in the set S, \({{\bf{s}}_{\bf{0}}}\) is not a final state.

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

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

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

\({{\bf{s}}_{\bf{3}}}\) shows that the string contains 101. \({{\bf{s}}_{\bf{3}}}\)has to be the final state as I am interested in strings containing 101.

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

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

I move from \({{\bf{s}}_{\bf{2}}}\)to\({{\bf{s}}_{\bf{3}}}\) , if I come across a 1, 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{1}}}\)
\({{\bf{s}}_{\bf{2}}}\)	\({{\bf{s}}_{\bf{0}}}\)	\({{\bf{s}}_{\bf{3}}}\)
\({{\bf{s}}_{\bf{3}}}\)	\({{\bf{s}}_{\bf{2}}}\)	\({{\bf{s}}_{\bf{3}}}\)

Therefore, this is the required construction.