The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+20 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.

  $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$
asked in Theory of Computation by Veteran (59.5k points)
edited by | 1.7k views
but turing machine does not accept epsilon

3 Answers

+15 votes
Best answer

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

answered by Junior (793 points)
edited 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 ?

Please Help.

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


See Here

+6 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. 

answered by Loyal (8.3k points)
+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
answered by Active (4k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

38,058 questions
45,554 answers
48,909 users