Question

Construct a deterministic finite-state automaton that recognizes the set of bit strings that start with 1 and end with 1.

Short answer

Therefore, the required deterministic finite-state automaton is shown below.

Step-by-step solution

General form

Finite-state automaton (Definition): A finite-state automaton \({\bf{M = }}\left( {{\bf{S,I,f,}}{{\bf{s}}_{\bf{0}}}{\bf{,F}}} \right)\) is made up of an initial or start state \({{\bf{s}}_0}\), a transition function f that assigns the next state to every pair of states and input (such that \({\bf{f:S \times I}} \to {\bf{S}}\)), a finite set S of states, a finite alphabet of inputs I, and a subset F of S made up of final states (or accepting states).

Deterministic finite-state automaton\({\bf{M = }}\left( {{\bf{S,I,f,}}{{\bf{s}}_{\bf{0}}}{\bf{,F}}} \right)\): a five-tuple consisting of a starting state\({{\bf{s}}_{\bf{0}}}\), a set of final states F, an alphabet of inputs I, a transition function f that assigns a new state to each pair of states and inputs, and a set of final states S

Step 2: Construct the deterministic finite-state automaton

Given that, the set of bit strings starts with 1 and ends with 1.

Let us construct the deterministic finite-state automaton by using the given information.

Construction:

Assume \({{\bf{s}}_0}\) is the initial state.

\({{\bf{s}}_0}\)shouldn't be a final state because the empty string shouldn't be permitted.

If the input begins with a0, we go to some non-final state \({{\bf{s}}_1}\) (since the string with a 0 and should thus never be recognized). Since the string does not begin with a 1, once we enter as\({{\bf{s}}_1}\), we never exit the state again.

A final state,\({{\bf{s}}_2}\), is reached if the input begins with a 1(as the string 1 should be recognized).

Remain in the final state \({{\bf{s}}_2}\) if the next input is another 1(as the string both starts and ends with a 1).

We change to a non-final state \({{\bf{s}}_3}\) if the subsequent input is a 0 (as the string ends with a 0 and should thus not be recognized).

If the input is 0 when we are in the non-final state \({{\bf{s}}_3}\) then we stay in \({{\bf{s}}_3}\) (as the string still ends with a 0).

When the input is 1 when we are in the non-final state\({{\bf{s}}_3}\), we return to \({{\bf{s}}_2}\) (as the string at that moment starts and ends with a 1).

Then, every string containing a 1 at the beginning or end should be accepted by the resulting deterministic finite-state automaton.

The diagram of the deterministic finite-state automaton is shown below.

Hence, the required deterministic finite-state automaton is founded.