1. Consider the following Turing MachineM = (Q, !,#,^, !, q0, F), where^ = {7, 8, 9} and! = {1, 2, 7, 8, 9,#}:Here, a transition of the form 9/1,R means that when the head is reading 9, M can legally write 1 and move right. Blank is denoted by #.
(a) Trace the computation ofM on input string 99888877 by completing the following derivation (the location [2] of the head is denoted by underlining the respective symbol):
q0#99888877# ` q1#99888877# ` q2#19888877# ` · · ·
Is the input string accepted?
(b) Explain informally, the working of the machine M. [4]
(c) Give the language L(M) in set notation. [3]
(d) Provide a grammar having 10 or less rules that accepts the same language as M. What type of grammar [6] is it?
(e) What properties of formal languages would you use (and how) to formally prove that there is no NFA that [4] can accept the language L(M). Explain briefly (note: you do not need to actually do any proof).
(f) Does there exist a PDA that accepts L(M)? Briefly explain your answer in one short sentence. [3]
(g) We obtain Turing Machine M0 by modifying M as follows: (a) replace transition 7/7,R from state q1 to [3] q5 with transition 2/2,R; and (b) delete loop transition 7/7,R in state q5. Give the language L(M0) in set notation.
2. Show formally, by resorting to problem reduction, that the problem, of deciding whether a Turing machine halts [8] on some input of length divisible by 3, is undecidable.