2.4k views

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 | 2.4k views
+3
but turing machine does not accept epsilon
0
When a Tm goes to a dead state i.e no transition mentioned then Is this TM halt?

Option A. Or epsilon is only accepted i.e tape contain B as the first character.

answered by Junior (747 points)
edited
0

But TM can't accept epsilon.

So is the transition on ∂(q0,B) valid ??

0
yeah, on this transition TM gets halted in q0. So, when string is empty i.e having all blanks on tape then it gets halted in q0
0

here epsilon is accepted ???  empty language is accepted r8??

0
I am unable to get to the answer of this question.
For a string B01B , how does it proceed?
q01B => 1q'1B => q11B .....
(take q as q0 and q' as q1)
it will be a never ending sequence
+2
What if we take the input as 11B ,

On the first 1 , it will transition to state q1.

On second 1 , it will transition back to state q0.

And when it finally encounters B as it is in state q0 , wont it halt ?

+5
@Harsh181996

Reply to ur comment..

What if we take the input as 11B ,

On the first 1 , it will transition to state q1. replace 1 with 1 .moves right.

On second 1 , it will transition back to state q0.replace 1 with 1 moves left.

(now u have to simulate above things inside input tape ...dont think like inputs of Finite Automata.)

Now after this we wont encounter B.. actually this is a loop.

U have again input 1 available at qo.
0
@rajesh ..how epsilon is accepting here
+2

@asu bhai

A TM for {ϵ} has pseudocode:

if tape[1] is blank then accept else reject


Which is happening over Here...

A TM for ∅ has pseudocode:

reject


See Here

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.

answered by Loyal (9.3k points)
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
answered by Active (3.9k points)

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!!

answered by (135 points)

1