edited by
11,717 views
41 votes
41 votes

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.

$$\begin{array}{|l|l|l|l|}\hline \text{}  &  \text{$0$} & \text{$1$} & \text{$B$} \\\hline \text{$q0$}  &  \text{$q1, 1, R$} & \text{$q1, 1, R$} & \text{$Halt$} \\\hline \text{$q1$}  &  \text{$q1, 1, R$} & \text{$q0, 1, L$} & \text{$q0, B, L$} \\\hline  \end{array}$$

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 page 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$?

  1. $M$ does not halt on any string in $(0+1)^+$
  2. $M$ does not halt on any string in $(00+1)^*$
  3. $M$ halts on all strings ending in a $0$
  4. $M$ halts on all strings ending in a $1$
edited by

5 Answers

Best answer
27 votes
27 votes

Correct Option: A

Or only epsilon is leading to a halting state as tape contain B as the first character.

edited by
16 votes
16 votes

Whenever B is given as a input, turing machine halts. This implies epsilon is only accepted when B occurs as an input. 
In positive closure, epsilon is not present. So, Turing machine never halts in case of (0+1)+.
 
Thus, option (A) is correct. 
 

3 votes
3 votes
this is correct

 

M does not halt on any string in (0+1)+

try it by make turing machine

this is true because oo11, 11 no halt will  be there

try it.

a option is correct
2 votes
2 votes

Construct TM with given table and see Epslon is accepted by Machine.

Now Option A,B,C are wrong bcoz all these options are contradictory

Epslon is in $(0+1)^{*}$

Epslon is not ending with 0.

Epslon is not ending with 1.

Hence, A is answer here!!

Answer:

Related questions

65 votes
65 votes
5 answers
2