UVa - cs302: Theory of Computation Spring 2008Exam 2Due: 8 April 2008Your Name:UVa Email Id:Honor Policy. For this exam, you must work alone. You may consult the single(two-sided) page of notes you brought, but may not look at any other materials oraid or accept aid from other students.Directions. Answer all four questions, including all sub-parts. You may use thebacks of pages for your scratch work, but we will only grade answers that arewritten in the answer boxes, or that are found following clearly marked arrowsfrom these boxes. The box for each answer is designed to be big enough to easilyfit a full credit, correct answer. If you feel like you need more space to write youranswer, then either your answer is incorrect, inelegant, or you are providing moredetail than needed for full credit.Question Target Score1 5-10-102 10-153 5-5-104 10-10-10Total 100Exam2-1Problem 1: Short Answers. (25) For each question, provide a correct, clear, precise,and concise answer from the perspective of a theoretical computer scientist.a. [5] What is a language?b. [10] Explain the essence of the Church-Turing Thesis in a way that would beunderstandable to a typical fifth grader.Exam2-2c. [10] What does it mean for a language to not be Turing-recognizable?Exam2-3Problem 2: Turing Machines. (25)a. [10] Provide an implementation-level description of a Turing machine that de-cides the language A = 0n1m0n/mwhere n ≥ 0 and m ≥ 1 (that is, the input isn zeros, followed by m ones, followed by n divided by m zeros). To be in thelanguage, n must be divisible by m. For example, strings in the language include00100, 00110, and 00001100; but the string 000110 is not in the language.Exam2-4b. [15] Define a cyclical Turing machine as a Turing machine with a one-way infinitetape (as in our standard Turing machine definition), except that the left edge be-havior is defined differently. Instead of staying in the leftmost square, if a cyclicalTuring machine would move left past the left edge of the tape, the head moves tothe rightmost non-blank square.Prove that the class of languages that can be recognized by a cyclical Turing ma-chine is identical to the class of languages that can be recognized by a regularTuring machine.Exam2-5Problem 3: Problematic Proofs. (20)Each of these “proofs” claims to prove a conjecture. Some of the conjectures arefalse, others may be true, but all the proofs are bad. For each proof, explain clearlywhy the provided proof does not satisfactorily prove the given conjecture. Youranswer should identify a fundamental flaw in the proof (for example, by explain-ing what it actually proves instead of the conjecture), not a minor issue like lack ofsufficient detail.a. [5] Conjecture: The set of languages that can be recognized by a deterministic push-down automaton is equivalent to the set of languages that can be recognized by a Turingmachine.Proof by Simulation. We prove the conjecture by showing how to simulate anyDPDA with a TM.We can simulate the stack by using the TM’s tape, writing a mark after the end ofthe input and then writing the stack from left to right on the TM tape. The top ofthe stack is represented by the leftmost square on the tape after the mark.To simulate a push, we move the tape head to the first blank, and then move rightto left copying the contents of each square into the square to its right. Then, we putthe pushed symbol in the leftmost square.To simulate a pop, we read the top of the stack, and then move left to right, copyingthe symbol in each square into the square to its left and overwriting the rightmostnon-blank square with a blank.To simulate the DPDA processing the input, we start by adding a dot to the firstinput symbol, and then mark each successive input symbol with a dot as the inputis processed from left to right.Thus, we can simulate a DPDA with a TM. This proves a DPDA is equivalent to aTM.Exam2-6b. [5] Conjecture: Define H(L) as the set of even-length strings in L. That is,H(L) = {w|w ∈ L and |w| = 2k for some k ≥ 0}H(L) is closed for context-free languages. (Note: this is based on the original un-corrected Exam 1 comments.)Proof: Since L is a CFL, there exists a DPDA M = (Q, Σ, Γ, δ, q0, F ) that recognizesL. We show how to construct a DPDA MH= (QH, Σ, Γ, δH, q0H, FH) that recog-nizes H(L). The basic idea is to make two copies the states of Q, corresponding tohaving seen an odd or even number of input symbols so far, and duplicating allthe transition rules.QH= Q × {even, odd} — states in MHkeep track of the state in M , andwhether an even or odd number of symbols have been seen so far.qOH= (q0, even)FH= {(qf, even)|qf∈ F } δHis defined by:δH((q, even), x, γ) = ((qr, odd), β) if δ(q, x, γ) → (qr, β)δH((q, odd), x, γ) = ((qr, even), β) if δ(q, x, γ) → (qr, β)Exam2-7c. [10] Conjecture: The “Busy Bee” language, defined below, is undecidable:LBusyBee= {hM, w, ki} where M describes a Turing machine, and k isthe number of different FSM states M enters before halting on inputw. (Note that qAcceptand qRejectare counted as states for the numberof different states count.)Proof by Reduction. We prove that LBusyBeeis undecidable by reducing HALTT Mto it.Construct MBusyBeegiven a machine MHALTthat decides HALTT M:MBusyBee=Simulate MHALTon input hM, wi.If MHALTaccepts, simulate M on w. On a second tape, list the states ofM, and add a mark on each state that is entered. Count the num-ber of marked states on the second tape. If the number matches k,accept.Otherwise, reject (without simulating M on w since it does not halt).Since building MBusyBeerequires MHALT, which we know does not exist, this provesthat LBusyBeeis undecidable.Exam2-8Problem 4: Decidability. (30) For each part, state clearly whether the describedlanguage is decidable or undecidable. Support your answer with a convincing proof.You may use any of the theorems we have proven in class or in the book, but youmay not use Rice’s theorem in your proof unless you also include a proof of Rice’stheorem.a. [10] LONGERDF A= {hA, Bi} where A and B are descriptions of DFAs and thelongest string that is accepted by A is longer than the longest string that is acceptedby B.Exam2-9b. [10] NOT SUBT M= {hA, Bi} where A and B are descriptions of Turing ma-chines and there is some string w which is accepted by A that is not accepted by B(that is, the language accepted by A is not a subset of the language accepted by B).Exam2-10c. [10] LBusyBee= {hM, w, ki} where M