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

 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
but turing machine does not accept epsilon

option A. or  epsilon is only accepted i.e tape contain B as the first character
selected by

But TM can't accept epsilon.

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

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

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

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

@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.
@rajesh ..how epsilon is accepting here

@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