Q. 87 A single tape Turing Machine M has two states q0 and q1, of which q0 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
The table is interpreted as illustrated below.
The entry (q1,1,R) in row q0 and column 1 signifies that if M is in state q0 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 q1.
Which of the following statements is true about M?
(A) M does not halt on any string in (0 + 1)+
(B) M dies not halt on any string in (00 + 1)*
(C) M halts on all string ending in a 0
(D) M halts on all string ending in a 1
Answer: (A)
Explanation:
