Question

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

a. 0.

b. 00.

c. 000.

d. 000000.

Short answer

a. 0, the sequence is, $\mathrm{q}0,\mathrm{IIqII},\mathrm{II}{\mathrm{IIq}}_{\mathrm{accept}}$.

b. 00 the sequence is, ${\mathrm{q}}_{1}00,{\mathrm{q}}_{2}0,{\mathrm{IIxq}}_3\mathrm{II},{\mathrm{IIq}}_5\mathrm{xII},{\mathrm{IIq}}_5\mathrm{xII},{\mathrm{IIq}}_2\mathrm{xII},{\mathrm{IIxq}}_2\mathrm{II},\mathrm{IIxII}{\mathrm{q}}_{\mathrm{accept}}$.

c. 000 the sequence is, ${\mathrm{q}}_{1}000,{\mathrm{IIq}}_{2}00,{\mathrm{IIxq}}_{3}0,\mathrm{IIx}0{\mathrm{q}}_4\mathrm{II},\mathrm{IIx}0\mathrm{II}{\mathrm{q}}_{\mathrm{reject}}$.

d. 000000 the sequence is,

$$\begin{gathered} {\mathrm{q}}_{1}000000,{\mathrm{IIq}}_{2}00000,{\mathrm{IIxq}}_{3}0000\mathrm{II},\mathrm{xII}0{\mathrm{q}}_{4}000 \\ \mathrm{IIx}0{\mathrm{xq}}_{3}00\mathrm{x},\mathrm{IIx}0\mathrm{x}0{\mathrm{q}}_4,\mathrm{IIx}0\mathrm{x}0{\mathrm{xq}}_3\mathrm{II},\mathrm{IIx}0{\mathrm{q}}_5\mathrm{xII} \\ \mathrm{IIx}0{\mathrm{q}}_5\mathrm{x}0\mathrm{xII},{\mathrm{IIxq}}_{5}0\mathrm{x}0\mathrm{xII},\mathrm{IIx}0{\mathrm{q}}_5\mathrm{x}0\mathrm{xII},{\mathrm{IIq}}_5\mathrm{x}0\mathrm{x}0\mathrm{xII}, \\ {\mathrm{IIxq}}_{2}0\mathrm{x}0\mathrm{xII},{\mathrm{IIxxq}}_3\mathrm{x}0\mathrm{xII},{\mathrm{IIxxxq}}_{3}0\mathrm{xII},\mathrm{IIxxx}0{\mathrm{q}}_4\mathrm{xII}, \\ \mathrm{IIxxx}0{\mathrm{xIIq}}_{\mathrm{reject}} \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.

Solution for part a.

a)

0, Here the sequence of configurations that M₂ enters when started on the indicated input string. Through the state diagram mention in the question, and

Here, the sequence is, ${\mathrm{q}}_{1}0,{\mathrm{IIq}}_2\mathrm{II},\mathrm{II}{\mathrm{IIq}}_{\mathrm{accept}}$.

Solution for part b.

b)

00, Here the sequence of configurations that M₂ enters when started on the indicated input string

00 the sequence is, ${\mathrm{q}}_{1}00,{\mathrm{q}}_{2}0,{\mathrm{IIxq}}_3\mathrm{II},{\mathrm{IIq}}_5\mathrm{xII},{\mathrm{IIq}}_5\mathrm{xII},{\mathrm{IIq}}_2\mathrm{xII},{\mathrm{IIxq}}_2\mathrm{II},\mathrm{IIxII}{\mathrm{q}}_{\mathrm{accept}}$.

Solution for part c.

c)

000, Here the sequence of configurations that M₂ enters when started on the indicated input string

Here, 000 the sequence is,

${\mathrm{q}}_{1}000,{\mathrm{IIq}}_{2}00,{\mathrm{IIxq}}_{3}0,\mathrm{IIx}0{\mathrm{q}}_4\mathrm{II},\mathrm{IIx}0\mathrm{II}{\mathrm{q}}_{\mathrm{reject}}$

Solution for part d.

d)

000000, Here the sequence of configurations that M₂ enters when started on the indicated input string

And here for this, 000000 the sequence is,

$$\begin{gathered} {\mathrm{q}}_{1}000000,{\mathrm{IIq}}_{2}00000,{\mathrm{IIxq}}_{3}0000\mathrm{II},\mathrm{xII}0{\mathrm{q}}_{4}000 \\ \mathrm{IIx}0{\mathrm{xq}}_{3}00\mathrm{x},\mathrm{IIx}0\mathrm{x}0{\mathrm{q}}_4,\mathrm{IIx}0\mathrm{x}0{\mathrm{xq}}_3\mathrm{II},\mathrm{IIx}0{\mathrm{q}}_5\mathrm{xII} \\ \mathrm{IIx}0{\mathrm{q}}_5\mathrm{x}0\mathrm{xII},{\mathrm{IIxq}}_{5}0\mathrm{x}0\mathrm{xII},\mathrm{IIx}0{\mathrm{q}}_5\mathrm{x}0\mathrm{xII},{\mathrm{IIq}}_5\mathrm{x}0\mathrm{x}0\mathrm{xII}, \\ {\mathrm{IIxq}}_{2}0\mathrm{x}0\mathrm{xII},{\mathrm{IIxxq}}_3\mathrm{x}0\mathrm{xII},{\mathrm{IIxxxq}}_{3}0\mathrm{xII},\mathrm{IIxxx}0{\mathrm{q}}_4\mathrm{xII}, \\ \mathrm{IIxxx}0{\mathrm{xIIq}}_{\mathrm{reject}} \end{gathered}$$