The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

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

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

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

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.

@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.2k
- Engineering Mathematics 4.7k
- Digital Logic 1.9k
- Programming & DS 3.5k
- Algorithms 3k
- Theory of Computation 3.7k
- Compiler Design 1.5k
- Databases 2.8k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 835
- Others 1.2k
- Admissions 263
- Exam Queries 390
- Tier 1 Placement Questions 17
- Job Queries 50
- Projects 6

33,593 questions

40,128 answers

114,021 comments

38,389 users