Question

Consider machine M (Q. Σ , Γ, δ, q1, qaccept, qreject), where Q ,{qi, q2, gs, qaccept, qreject}, Σ as follows: { 0.1 } , Γ { 0.1 U } , and the transition function δ is δ (qi. Ú)-(qreject, U, R) δ (qi, 0)-(P-0, R) -(Gaccept, Prove that M is NOT a decider Describe in mathematical terms the language A that M recognises, and verify 1. your answer, ie prove that A- L(M)

Answer 1

The given Turing machine is :

0 ->0,R U > UR 0->O,R 1-1,R q21-1,R 0->0.R 1-1,R 93 U-> U,R U-> U,R gaccep qrejec

i) if our input string is of the form 1ⁿ0^m1^p, then it goes to state q3 and loops there without going to reject state.

So this is not a decider Turing machine.

ii) This Turing machine recognizes the strings of {0,1}* of the form 1ⁿ0^m and rejects empty string.

So the language A = { 1ⁿ0^m | n,m are positive integers, > 0 }