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
Get step-by-step solutions from verified subject matter experts
