2k 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.

 $0$ $1$ $B$ $q0$ $q1, 1, R$ $q1, 1, R$ $Halt$ $q1$ $q1, 1, R$ $q0, 1, L$ $q0, B, L$

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 | 2k views
+1
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.

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 ?

+2
@Harsh181996

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
+1

@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.

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

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.

1