The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+21 votes
1.8k 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$
asked in Theory of Computation by Veteran (59.6k points)
edited by | 1.8k views
+1
but turing machine does not accept epsilon

4 Answers

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

@Kapilp 

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 ?

Please Help.
+2
@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
+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

+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.5k 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 (4.2k points)
0 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!!

answered ago by (25 points)
Answer:

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

41,082 questions
47,677 answers
147,481 comments
62,393 users