Question

Construct a deterministic finite-state automaton that recognizes the set of all bit strings that end with 10.

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

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 that the last two digits were 01.

\({{\bf{s}}_{\bf{2}}}\)gives that the last two digits were 10.\({{\bf{s}}_{\bf{2}}}\) has to be the final state as I interested in string ending with 10.

\({{\bf{s}}_{\bf{3}}}\)show that the last two digits were 11.

As I move from \({{\bf{s}}_{\bf{i}}}\)to\({{\bf{s}}_{\bf{j}}}\) due to input z if \({{\bf{s}}_{\bf{i}}}\) represented that the last two digits xy and \({{\bf{s}}_{\bf{j}}}\)represents that the last two digits are yz.

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

Therefore, this can be the required construction.