The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+19 votes
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
asked in Theory of Computation by Veteran (69k points) | 1.4k 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 (831 points)
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

@Kapilp 

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

+4 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 Boss (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 Loyal (4.7k 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

33,593 questions
40,128 answers
114,021 comments
38,389 users