Question

Construct a deterministic finite-state automaton that recognizes the set of all bit strings that begin with 0 or with 11.

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

Let 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 it moves on to a non-final state \({{\bf{s}}_{\bf{1}}}\). It moves on to the final state \({{\bf{s}}_{\bf{2}}}\),if the next digit is a 1. The state \({{\bf{s}}_{\bf{2}}}\)or \({{\bf{s}}_{\bf{3}}}\),It will remain in these states.

If the input starts with a 0, then it moves on to a non-final state \({{\bf{s}}_{\bf{2}}}\). It will remain in this state.

Sketch of deterministic finite-state automaton.

The sketch of deterministic finite-state automation can be drawn by four states. The sketch is

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

Therefore, this is the require construction.