Question

A single tape Turning Machine M has two states q₀ and q₁, of which q₀ is the starting state. The tape alphabet of M is {0, 1, B} and its input alphabet is {0, 1}. The symbol B is the blank symbol used to indicate end of an input string The transition function of M is described in the following table:

	0	1	B
q0	q1, 1, R	q1 ,1, R	Halt
q1	q1 ,1, R	q0, 1, L	q0, B, L

The table is interpreted as illustrated below. The entry (q₁, 1 , R) in row q₀ and column 1 signifies that if M is in state q₀ and reads 1 on the current tape square, then it writes 1 on the same tape square, moves its tape head one position to the right and transitions to state q₁. Which of the following statements is true about M?

Answer 1

Transition function of M

	0	1	B
q0	q1, 1, R	q1 ,1, R	Halt
q1	q1 ,1, R	q0, 1, L	q0, B, L

The graphic representation of M is as follows:

This machine hangs on every string in (0+1)^*.
Example is shown below for the strings "00" and "01".