Question

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

Short answer

The result is

State	0	1
\({{\mathbf{s}}_{\mathbf{0}}}\)	\({{\mathbf{s}}_{\mathbf{3}}}\)	\({{\mathbf{s}}_{\mathbf{1}}}\)
\({{\mathbf{s}}_{\mathbf{1}}}\)	\({{\mathbf{s}}_{\mathbf{3}}}\)	\({{\mathbf{s}}_{\mathbf{2}}}\)
\({{\mathbf{s}}_{\mathbf{2}}}\)	\({{\mathbf{s}}_{\mathbf{6}}}\)	\({{\mathbf{s}}_{\mathbf{2}}}\)
\({{\mathbf{s}}_{\mathbf{3}}}\)	\({{\mathbf{s}}_{\mathbf{3}}}\)	\({{\mathbf{s}}_{\mathbf{3}}}\)
\({{\mathbf{s}}_{\mathbf{4}}}\)	\({{\mathbf{s}}_{\mathbf{4}}}\)	\({{\mathbf{s}}_{\mathbf{5}}}\)
\({{\mathbf{s}}_{\mathbf{5}}}\)	\({{\mathbf{s}}_{\mathbf{2}}}\)	\({{\mathbf{s}}_{\mathbf{6}}}\)
\({{\mathbf{s}}_{\mathbf{6}}}\)	\({{\mathbf{s}}_{\mathbf{4}}}\)	\({{\mathbf{s}}_{\mathbf{5}}}\)

Step-by-step solution

Construction of deterministic finite-state automaton.

Let \(\mathbf{S=\{11\}\{0,1\}*\{11\}}\).

Let us consider states are \({{\mathbf{s}}_{\mathbf{0}}}\mathbf{,}{{\mathbf{s}}_{\mathbf{1}}}\mathbf{,}{{\mathbf{s}}_{\mathbf{2}}}\mathbf{,}{{\mathbf{s}}_{\mathbf{3}}}\mathbf{,}{{\mathbf{s}}_{\mathbf{4}}}\mathbf{,}{{\mathbf{s}}_{\mathbf{5}}}\mathbf{,}{{\mathbf{s}}_{\mathbf{6}}}\).

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

The state \({{\mathbf{s}}_{\mathbf{1}}}\) has the first and last two digits were 11.

The state \({{\mathbf{s}}_{\mathbf{2}}}\) give that the first and last two digits were 01.

The state \({{\mathbf{s}}_{\mathbf{3}}}\) shows that the first digits is 0 and last digits are 01.

The state \({{\mathbf{s}}_{\mathbf{4}}}\)has that the last two digits are 00.

The state \({{\mathbf{s}}_{\mathbf{5}}}\) gives that the last two digits are 01.

The state \({{\mathbf{s}}_{\mathbf{6}}}\) shows that the last two digits are 10.

If the input starts with a 1, then it moves on to a non-final state\({{\mathbf{s}}_{\mathbf{3}}}\). Once it is at state, it will remain at this state\({{\mathbf{s}}_{\mathbf{3}}}\).

If the input start with a 1, then it moves on to a non-final state\({{\mathbf{s}}_{\mathbf{1}}}\). It moves on to the final state \({{\mathbf{s}}_{\mathbf{2}}}\), if the next digit is a 1, else it moves on to the non-final state \({{\mathbf{s}}_{\mathbf{3}}}\).

Next, it moves between \({{\mathbf{s}}_{\mathbf{2}}}\mathbf{,}{{\mathbf{s}}_{\mathbf{3}}}\mathbf{,}{{\mathbf{s}}_{\mathbf{4}}}\mathbf{,}{{\mathbf{s}}_{\mathbf{5}}}\mathbf{,}{{\mathbf{s}}_{\mathbf{6}}}\) and keep track of the last two digits.

The state \({{\mathbf{s}}_{\mathbf{2}}}\) will be the final state, because if it arrives at state \({{\mathbf{s}}_{\mathbf{2}}}\), then the string begins with 11 and ends with 11.

Sketch of deterministic finite-state automaton.

The sketch of deterministic finite-state automation can be drawn by seven states\({{\mathbf{s}}_{\mathbf{0}}}\mathbf{,}{{\mathbf{s}}_{\mathbf{1}}}\mathbf{,}{{\mathbf{s}}_{\mathbf{2}}}\mathbf{,}{{\mathbf{s}}_{\mathbf{3}}}\mathbf{,}{{\mathbf{s}}_{\mathbf{4}}}\mathbf{,}{{\mathbf{s}}_{\mathbf{5}}}\mathbf{,}{{\mathbf{s}}_{\mathbf{6}}}\). The sketch is

Other way of representing in tabular form.

State	0	1
\({{\mathbf{s}}_{\mathbf{0}}}\)	\({{\mathbf{s}}_{\mathbf{3}}}\)	\({{\mathbf{s}}_{\mathbf{1}}}\)
\({{\mathbf{s}}_{\mathbf{1}}}\)	\({{\mathbf{s}}_{\mathbf{3}}}\)	\({{\mathbf{s}}_{\mathbf{2}}}\)
\({{\mathbf{s}}_{\mathbf{2}}}\)	\({{\mathbf{s}}_{\mathbf{6}}}\)	\({{\mathbf{s}}_{\mathbf{2}}}\)
\({{\mathbf{s}}_{\mathbf{3}}}\)	\({{\mathbf{s}}_{\mathbf{3}}}\)	\({{\mathbf{s}}_{\mathbf{3}}}\)
\({{\mathbf{s}}_{\mathbf{4}}}\)	\({{\mathbf{s}}_{\mathbf{4}}}\)	\({{\mathbf{s}}_{\mathbf{5}}}\)
\({{\mathbf{s}}_{\mathbf{5}}}\)	\({{\mathbf{s}}_{\mathbf{2}}}\)	\({{\mathbf{s}}_{\mathbf{6}}}\)
\({{\mathbf{s}}_{\mathbf{6}}}\)	\({{\mathbf{s}}_{\mathbf{4}}}\)	\({{\mathbf{s}}_{\mathbf{5}}}\)

Therefore, this is the require construction.