Automata: Turing Machine Question....... Hi there, I could use some help with th

Question

Automata: Turing Machine Question.......

Hi there, I could use some help with this problem. I was thinking C. is the answer, but I don't know for sure. Which one would be the correct answer? Could you explain why it would be the right answer, it would be very helpful!

Thanks!

A non deterministic Turing machine Mwith start state qo and accepting state qf has the following transition function: (q,a) 90 ((q1,0,R)) (q 1,0,R)) (q 1,0,R)) q1 Deduce what Mdoes on any input of 0's and 1's. Demonstrate your understanding by identifying, from the list below, the ID that CANNOT be reached on some number of moves from the initial ID q0010101 C a 0qfl 1111 O b) q011 1111 c) 0qfl 111111 d) 0111 1111q1

Explanation / Answer

I would say Answer is b

Reason : Since it is no deterministic,

LET us suppose we are in this state

q20 111111

On taking q2, on input 0 it goes to qf and always MOVES RIGHT, in no way it will reach before 0 like qf0 (Never)




It will always move to its right, after consuming an input 0.

So the answer is B

A is fine, C is fine, D is fine...

B will never occur, See the Transition table ..we can go to qf only through q2 and it moves right after that, So Thats why B

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.