Question: A Turing machine M with start state q0 and accepting state q f has the following transition function: (q,a) 0 1 B q 0 (q

A Turing machine M with start state q0 and accepting state qf has the following transition function:

(q,a) 0 1 B

q0 (q0,1,R) (q1,1,R) (qf,B,R)

q1 (q2,0,L) (q2,1,L) (q2,B,L)

q2 - (q0,0,R) -

qf - - -

Deduce what M does on any input of 0's and 1's. Hint: consider what happens when M is started in state q0 at the left end of a sequence of any number of 0's (including zero of them) and a 1. Demonstrate your understanding by identifying the true transition of M from the list below.

a) q00101 |-* 1010qf

b) q00011 |-* 1100Bqf

c) q01010 |-* 1101Bqf

d) q01010 |-* 1001Bqf

Explain me the ans plz

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Databases Questions!