Question: Consider machine M = (Q, sigma, Gamma, delta, q_0, q_accept, q_reject), where Q ={q_0, q_1, q_2, q_accept. q_reject}. sigma = {0, 1}, Gamma = {0,

Consider machine M = (Q, sigma, Gamma, delta, q_0, q_accept, q_reject), where Q ={q_0, q_1, q_2, q_accept. q_reject}. sigma = {0, 1}, Gamma = {0, 1, U}, and transition function delta is defined as follows: delta (q_0, 0) = (q_3, 0, R) delta (q_0, 1) = (q_0. 1.L) delta(q_0, U) = (q_0, U, R) delta(q_1, 0) = (q_1, 0, R) delta (q_1, 1) = (q_1, 1. R) delta (q_1, U) = (q_2, U, L) delta (q_2, 0) = (q_reject. U, R) delta (q_2, 1) = (q_accept. U, R) delta (q_2, U) = (q_2, U, R) (a) Prove that M is NOT a decider. (b) Describe in mathematical terms the language L that M recognizes, and verify your answer, i.e. prove that L = L(M). (c). Is L Turing-decidable? [No need to give a formal proof, but provide clear reasons for your answer.]
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
