The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

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

- $M$ does not halt on any string in $(0+1)^+$
- $M$ does not halt on any string in $(00+1)^*$
- $M$ halts on all strings ending in a $0$
- $M$ halts on all strings ending in a $1$

+15 votes

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

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

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.

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.

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.

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.1k
- Digital Logic 2k
- Programming & DS 3.7k
- Algorithms 3.1k
- Theory of Computation 3.9k
- Compiler Design 1.5k
- Databases 2.9k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 1k
- Others 1.3k
- Admissions 447
- Exam Queries 428
- Tier 1 Placement Questions 17
- Job Queries 55
- Projects 8

35,487 questions

42,746 answers

121,459 comments

42,138 users