-
A single tape turing maching 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?
-
- M does not halt on any string in (0 + 1)+
- M does not halt on any string in (00 + 1)*
- M halts on all strings ending in a 0
- M halts on all strings ending in a 1
- M does not halt on any string in (0 + 1)+
Correct Option: A
This turning machine starts at 90 if it doesn't get any input symbol but B then it stops.
So if (00 + 1) * is chosen then the M/C can halt. Option (b) is wrong.
Option (c) & (d) are possible but not necessary.
Option (a) (0 + 1) * 1 or more occurrence of 0 or 1.
So 0, 1, 00, 01, 10, 11........are valid strings & the machine doesn't halt for them.
Hence (a) is correct option
