Question

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

Short answer

The result is:

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

If the input starts with a 1, then I move on to a non-final state \({{\bf{s}}_{\bf{1}}}\) and remain there no matter what the next bits are.

If the input starts with a0, then I move on to a non-final state \({{\bf{s}}_{\bf{2}}}\). If the next digit is a 0, then I move on to \({{\bf{s}}_{\bf{1}}}\) and remain there no matter what the next bits are. If the next digit was a 1, then I move to the final state \({{\bf{s}}_{\bf{3}}}\) and remain there no matter what the next bits are.

Sketch of deterministic finite-state automaton.

Another way of representing in tabular form.

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

Therefore, this is the required construction.