Question

Construct a Turing machine that recognizes the set of all bit strings that end with a \({\bf{0}}\).

Short answer

The constructed Turing machine that recognizes the set of all bit strings that end with a\({\bf{0}}\)is

\(\begin{array}{c}{\bf{T = }}\left( {{\bf{S,I,f,}}{{\bf{s}}_{\bf{0}}}} \right)\\{\bf{S = }}\left\{ {{{\bf{s}}_{\bf{0}}}{\bf{,}}{{\bf{s}}_{\bf{1}}}{\bf{,}}{{\bf{s}}_{\bf{2}}}} \right\}\\{\bf{I = \{ 0,1,B\} }}\\\left( {{{\bf{s}}_{\bf{0}}}{\bf{,0,}}{{\bf{s}}_{\bf{0}}}{\bf{,0,R}}} \right)\\\left( {{{\bf{s}}_{\bf{0}}}{\bf{,1,}}{{\bf{s}}_{\bf{0}}}{\bf{,1,R}}} \right)\\\left( {{{\bf{s}}_{\bf{0}}}{\bf{,B,}}{{\bf{s}}_{\bf{1}}}{\bf{,B,R}}} \right)\\\left( {{{\bf{s}}_{\bf{1}}}{\bf{,1,}}{{\bf{s}}_{\bf{1}}}{\bf{,1,R}}} \right)\\\left( {{{\bf{s}}_{\bf{1}}}{\bf{,0,}}{{\bf{s}}_{\bf{2}}}{\bf{,1,R}}} \right)\end{array}\)

Step-by-step solution

Definition

A Turing machine \({\bf{T = }}\left( {{\bf{S,I,f,}}{{\bf{s}}_{\bf{0}}}} \right)\) contains a finite set \({\bf{S}}\) of states, an alphabet \({\bf{I}}\) containing the blank symbol \({\bf{B}}\), a starting state \({{\bf{s}}_{\bf{0}}}\) and a partial function from \(S{\bf{ \times I}}\) to \({\bf{S \times I \times }}\{ R,L\} \). Note: The partial function \({\bf{f}}\) is often represented as \(5{\bf{ - }}\)tuples.

It will require \(3\) states \({{\bf{s}}_{\bf{0}}}\), \({{\bf{s}}_{\bf{1}}}\) and \({{\bf{s}}_{\bf{2}}}\)\({{\bf{s}}_{\bf{0}}}\) is the start state, \({{\bf{s}}_{\bf{1}}}\) will be the state that indicates that the end of the input was reached, and \({{\bf{s}}_{\bf{2}}}\) will be the final state), which will be contained in the set \({\bf{S}}\).

\({\bf{S = }}\left\{ {{{\bf{s}}_{\bf{0}}}{\bf{,}}{{\bf{s}}_{\bf{1}}}{\bf{,}}{{\bf{s}}_{\bf{2}}}} \right\}\)

The alphabet \({\bf{I}}\) needs to contain the tape symbols. The tape symbols are given as \(0,1\)and\({\bf{B}}\).

\({\bf{I = \{ 0,1,B\} }}\)

Defining the partial function as five-tuples

Next, it will define the partial function as five-tuples.

As long as the input is a \(0\) or a \(1\), it will keep the input unchanged and move one position to the right.

\(\begin{array}{c}\left( {{{\bf{s}}_{\bf{0}}}{\bf{,0,}}{{\bf{s}}_{\bf{0}}}{\bf{,0,R}}} \right)\\\left( {{{\bf{s}}_{\bf{0}}}{\bf{,1,}}{{\bf{s}}_{\bf{0}}}{\bf{,1,R}}} \right)\end{array}\)

Once it arrives at the first blank symbol, it will move to the state \({{\bf{s}}_{\bf{1}}}\) as itis at the end of the string. It also moves one position to the left on thetape such that it can check the value of the last digit in the state \({{\bf{s}}_{\bf{1}}}\).

\(\left( {{{\bf{s}}_{\bf{0}}}{\bf{,B,}}{{\bf{s}}_{\bf{1}}}{\bf{,B,R}}} \right)\)

Defining the partial function as five-tuples

Once itis at state \({{\bf{s}}_{\bf{1}}}\), it knows that the current input will be the last digit of the input. If the input is a \(1\), then it remains at the non-final state \({{\bf{s}}_{\bf{1}}}\) such that the string won't be accepted.

\(\left( {{{\bf{s}}_{\bf{1}}}{\bf{,1,}}{{\bf{s}}_{\bf{1}}}{\bf{,1,R}}} \right)\)

If the input is \(0\) at state \({{\bf{s}}_{\bf{1}}}\), then it moves to the final state \({{\bf{s}}_{\bf{2}}}\) as the string ends with a \(0\) and thus should be recognized by the Turing machine.

\(\left( {{{\bf{s}}_{\bf{1}}}{\bf{,0,}}{{\bf{s}}_{\bf{2}}}{\bf{,1,R}}} \right)\)

Once itis in the final state \({{\bf{s}}_{\bf{2}}}\), the machine will need to halt as it knows that the string ends with a \(0\). This will occur when it does not add a five-tuple that has \({{\bf{s}}_{\bf{2}}}\) as its first coordinate.

Hence, the constructed Turing machine that recognizes the set of all bit strings that end with a\({\bf{0}}\)is

\(\begin{array}{c}\left( {{{\bf{s}}_{\bf{0}}}{\bf{,0,}}{{\bf{s}}_{\bf{0}}}{\bf{,0,R}}} \right)\\\left( {{{\bf{s}}_{\bf{0}}}{\bf{,1,}}{{\bf{s}}_{\bf{0}}}{\bf{,1,R}}} \right)\\\left( {{{\bf{s}}_{\bf{0}}}{\bf{,B,}}{{\bf{s}}_{\bf{1}}}{\bf{,B,R}}} \right)\\\left( {{{\bf{s}}_{\bf{1}}}{\bf{,1,}}{{\bf{s}}_{\bf{1}}}{\bf{,1,R}}} \right)\\\left( {{{\bf{s}}_{\bf{1}}}{\bf{,0,}}{{\bf{s}}_{\bf{2}}}{\bf{,1,R}}} \right)\end{array}\)