Consider machine M =(Q, sigma, gamma, delta, q_0, q_reject), where Q = {q_0, q_1
ID: 3110593 • Letter: C
Question
Consider machine M =(Q, sigma, gamma, delta, q_0, 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_1, 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) = (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_accecpt, U, R) delta(q_2, U) = (q_2, U, R) Prove that M is NOT a decider. Describe in mathematical terms the language L that M recognises, and verify your answer, ie prove that L = angle (M). Is L Turing-decidable? [No need to give a formal proof, but provide clear reasons for your answer.]Explanation / Answer
(a)&(b)- The language L(M) consists of all binary strings which begin with the bit 0. To see this, note that if a string x begins with any symbol other than 0 then M cannot leave the initial state q0 on input x, so x L(M). On the other hand, if a binary x begins with one or more 0’s then by using the non-deterministic choice (q0, 1, R) (q0, 0) repeatedly the machine can convert all 0’s at the start to 1’s, and then arrive via (q1, 1, R) to be scanning the first nonzero symbol in state q1. In fact, this also works whenever M scans the start of a sequence of 0’s regardless of whether they are initial or not. If the next non-0 symbol is U then M accepts. If not, then it is 1 and M writes 0 there and by a sequence of moves (see †) returns to this 0 in state q0 without making any other changes to the string. Thus M may advance through the entire string until it reaches U is state q1, at which point it will transition to accepting. The sequence † of moves is: M writes a 0 in scanned cell (via (q2, 0, L) (q1, 1)) and steps to the left, where it finds a 1 by assumption. M is now in state q2 so this 1 will be retained and M will move to the right (using (q0, 1, R) (q2, 1)).
(c)-Lang L is Turing-decidable because TM M that decides L.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.