A single-tape Turing machine M has two states q0 and q1, with q0 as the start…
GATE · 2003 · CS
A single-tape Turing machine M has two states q0 and q1, with q0 as the start state. Its tape alphabet is {0, 1, B}, its input alphabet is {0, 1}, and B is the blank symbol that marks the end of the input. The transition function is:
State / read symbol | 0 | 1 | B |
|---|---|---|---|
q0 | q1, 1, R | q1, 1, R | Halt |
q1 | q1, 1, R | q0, 1, L | q0, B, L |
For example, the entry (q1, 1, R) in row q0 and column 1 means that M, while in q0 and reading 1, writes 1, moves one square to the right, and enters q1.
Which of the following statements is true about M?
- A.
M does not halt on any string in (0 + 1)+
- B.
M does not halt on any string in (00 + 1)*
- C.
M halts on all strings ending in a 0
- D.
M halts on all strings ending in a 1
Attempted by 67 students.
Sign up free to check your answer
Sign up freeLoading lesson…