Question

Answer and explain your answer

QUESTION 5 A Turing machine M with start state go and accepting state of has the following transition function: 1 8(q,a) 0 B 40 (90,1,R) (91,1,R) (9f,B,R) 91 (42,0,L) (42,1,L) (92,B,L) 42 (90,0,R) 9f Deduce what M does on any input of O's and I's. Hint: consider what happens when M is started in state qo 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. o 901100|-* 1111Bqf 900011 |-* 1100Bqf 900101 |-* 1110Bqf 901010* 01019f QUESTION 6 Lati warrume that all languages are gyer input alphabet {0,1}. Also, we assume that a Turing

Answer 1

The Correct Answer is (b):

q00011⊢*1100Bqf

Explanation: Consider the tracing of the input string 0011

q₀0011⊢1q₀011

⊢11q₀11

⊢111q₁1

⊢11q₂11

⊢110q₀1

⊢1101q₁B

⊢110q₂1B

⊢1100q₀B

⊢1100Bq_f