Question

This exercise concerns TM M₁, whose description and state diagram appear in Example 3.9. In each of the parts, give the sequence of configurations that M₁ enters when started on the indicated input string.

a. 11.

b. 1#1

c. 1##1

d. 10#11

e. 10#10

Short answer

a) 11, the sequence is given as, ${\mathrm{q}}_{1}11,{\mathrm{xq}}_{3}1,\mathrm{x}1{\mathrm{q}}_3\left|\mathrm{\_}\right|,\mathrm{x}1{\mathrm{q}}_{\mathrm{reject}}$.

b) 1#1,the sequence is given as,

${\mathrm{q}}_{1}1\#1\to {\mathrm{xq}}_3\#1\to \mathrm{x}\#{\mathrm{q}}_{5}1\to {\mathrm{xq}}_6\#\mathrm{x}\to {\mathrm{q}}_7\mathrm{x}\#\mathrm{x}\to {\mathrm{xq}}_1\#\mathrm{x}\to \mathrm{x}\#{\mathrm{q}}_8\mathrm{x}\to \mathrm{x}\#{\mathrm{q}}_8\#\to \mathrm{x}\#\mathrm{x}\#{\mathrm{q}}_{\mathrm{accept}}\#$

c) 1##1,the sequence is given as, ${\mathrm{q}}_{1}1\#\#1\to {\mathrm{xq}}_3\#\#1\to \mathrm{x}\#{\mathrm{q}}_5\#1\to \mathrm{x}\#\#{\mathrm{q}}_{\mathrm{reject}}1$

d) 10#11,the sequence is given as,

$$\begin{gathered} {\mathrm{q}}_{1}10\#11\to {\mathrm{xq}}_{1}0\#11\to \mathrm{x}0\mathrm{q}1\#11\to \mathrm{x}0\#{\mathrm{q}}_{5}11\to \mathrm{x}0{\mathrm{q}}_6\#\mathrm{x}1\to {\mathrm{xq}}_{7}0\#\mathrm{x}1\to {\mathrm{q}}_7\mathrm{x}0\#\mathrm{x}1 \\ \to {\mathrm{xq}}_{1}0\#\mathrm{x}1\to {\mathrm{xxq}}_2\#\mathrm{x}1\to \mathrm{xx}\#{\mathrm{q}}_4\mathrm{x}1 \\ \to \mathrm{xx}\#{\mathrm{xq}}_{4}1\to \mathrm{xx}\#\mathrm{x}1{\mathrm{q}}_{\mathrm{reject}} \end{gathered}$$

e) 10#10, the sequence is given as,

$$\begin{gathered} {\mathrm{q}}_{1}10\#10\to {\mathrm{xq}}_{3}0\#10\to {\mathrm{x}}_0{\mathrm{q}}_3\#10\to {\mathrm{x}}_0\#{\mathrm{q}}_{5}10\to {\mathrm{x}}_0{\mathrm{q}}_6\#{\mathrm{x}}_0\to {\mathrm{xq}}_{7}0\#{\mathrm{x}}_0\to {\mathrm{q}}_7{\mathrm{x}}_0\#{\mathrm{x}}_0 \\ \to {\mathrm{xq}}_{10}\#{\mathrm{x}}_0\to {\mathrm{xxq}}_2\#{\mathrm{x}}_0\to \mathrm{xx}\#{\mathrm{q}}_4{\mathrm{x}}_0\to \mathrm{xx}\#{\mathrm{xq}}_4\to \mathrm{xx}\#{\mathrm{q}}_6\mathrm{xx}\to {\mathrm{xxq}}_6\#\#\mathrm{xx}\to {\mathrm{xq}}_7\mathrm{x}\#\mathrm{xx} \\ \to {\mathrm{xxq}}_1\#\mathrm{xx}\to \mathrm{xx}\#{\mathrm{q}}_8\mathrm{xx}\to \mathrm{xx}\#{\mathrm{xq}}_8\mathrm{x}\to \mathrm{xx}\#{\mathrm{xxq}}_8\#\to \mathrm{xx}\#\mathrm{xx}\#{\mathrm{q}}_{\mathrm{accept}} \end{gathered}$$

Step-by-step solution

Turing machine.

A Turing Machine (TM) is a mathematical model which consists of an infinite length tape divided into cells on which input is given. It consists of a head which reads the input tape. A state register stores the state of the Turing machine.

As its state diagram is given in the example 3.9 is shown below,

Step 2:

a)

The sequence of configurations and the string which is accepted by the machine which is defined in example in above state diagram, that machine enters when started on the indicated input string and accepted by this Turing machine is given as,

11, the sequence is given as, ${\mathrm{q}}_{1}11,{\mathrm{xq}}_{3}1,\mathrm{x}1{\mathrm{q}}_3\left|\mathrm{\_}\right|,\mathrm{x}1{\mathrm{q}}_{\mathrm{reject}}$.

Step 3:

The sequence of configurations and the string which is accepted by the machine which is defined in example in above state diagram, that machine enters when started on the indicated input string and accepted by this Turing machine is given as,

1#1,the sequence is given as,

${\mathrm{q}}_{1}1\#1\to {\mathrm{xq}}_3\#1\to \mathrm{x}\#{\mathrm{q}}_{5}1\to {\mathrm{xq}}_6\#\mathrm{x}\to {\mathrm{q}}_7\mathrm{x}\#\mathrm{x}\to {\mathrm{xq}}_1\#\mathrm{x}\to \mathrm{x}\#{\mathrm{q}}_8\mathrm{x}\to \mathrm{x}\#{\mathrm{q}}_8\#\to \mathrm{x}\#\mathrm{x}\#{\mathrm{q}}_{\mathrm{accept}}\#$

Step 4:

c)

The sequence of configurations and the string which is accepted by the machine which is defined in example in above state diagram, that machine enters when started on the indicated input string and accepted by this Turing machine is given as,

1##1,the sequence is given as,

1##1, the sequence is given as,${\mathrm{q}}_{1}1\#\#1\to {\mathrm{xq}}_3\#\#1\to \mathrm{x}\#{\mathrm{q}}_5\#1\to \mathrm{x}\#\#{\mathrm{q}}_{\mathrm{reject}}1$

Step 5:

d)

10#11,

The sequence of configurations and the string which is accepted by the machine which is defined in example in above state diagram, that machine enters when started on the indicated input string and accepted by this Turing machine is given as,

The sequence is given as,

$$\begin{gathered} {\mathrm{q}}_{1}10\#11\to {\mathrm{xq}}_{1}0\#11\to \mathrm{x}0\mathrm{q}1\#11\to \mathrm{x}0\#{\mathrm{q}}_{5}11\to \mathrm{x}0{\mathrm{q}}_6\#\mathrm{x}1\to {\mathrm{xq}}_{7}0\#\mathrm{x}1\to {\mathrm{q}}_7\mathrm{x}0\#\mathrm{x}1 \\ \to {\mathrm{xq}}_{1}0\#\mathrm{x}1\to {\mathrm{xxq}}_2\#\mathrm{x}1\to \mathrm{xx}\#{\mathrm{q}}_4\mathrm{x}1 \\ \to \mathrm{xx}\#{\mathrm{xq}}_{4}1\to \mathrm{xx}\#\mathrm{x}1{\mathrm{q}}_{\mathrm{reject}} \end{gathered}$$

Step 6:

e)

10#10,

The sequence of configurations and the string which is accepted by the machine which is defined in example in above state diagram, that machine enters when started on the indicated input string and accepted by this Turing machine is given as,

The final sequence for this machine is given as,

$$\begin{gathered} {\mathrm{q}}_{1}10\#10\to {\mathrm{xq}}_{3}0\#10\to {\mathrm{x}}_0{\mathrm{q}}_3\#10\to {\mathrm{x}}_0\#{\mathrm{q}}_{5}10\to {\mathrm{x}}_0{\mathrm{q}}_6\#{\mathrm{x}}_0\to {\mathrm{xq}}_{7}0\#{\mathrm{x}}_0\to {\mathrm{q}}_7{\mathrm{x}}_0\#{\mathrm{x}}_0 \\ \to {\mathrm{xq}}_{10}\#{\mathrm{x}}_0\to {\mathrm{xxq}}_2\#{\mathrm{x}}_0\to \mathrm{xx}\#{\mathrm{q}}_4{\mathrm{x}}_0\to \mathrm{xx}\#{\mathrm{xq}}_4\to \mathrm{xx}\#{\mathrm{q}}_6\mathrm{xx}\to {\mathrm{xxq}}_6\#\#\mathrm{xx}\to {\mathrm{xq}}_7\mathrm{x}\#\mathrm{xx} \\ \to {\mathrm{xxq}}_1\#\mathrm{xx}\to \mathrm{xx}\#{\mathrm{q}}_8\mathrm{xx}\to \mathrm{xx}\#{\mathrm{xq}}_8\mathrm{x}\to \mathrm{xx}\#{\mathrm{xxq}}_8\#\to \mathrm{xx}\#\mathrm{xx}\#{\mathrm{q}}_{\mathrm{accept}} \end{gathered}$$