PROBLEM SET 5, CSC 280, 2006 DUE BEFORE CLASS, WED. MAR. 1 The fifth problem set is as follows. All 7 problems will be marked out of the same total. Answers to any 6 questions make a complete answer paper. However, you can do all questions to earn bonus points. Note that whenever you are asked to design a TM, what is meant is a 1-tape deterministic TM, unless specified otherwise. Keep your eyes on the instructor's and the TAs' web site for any corrections or discussion. PROBLEM 1 ~~~~~~~~~ a. Prove that a two-stack PDA is equivalent to a TM. b. Suppose that instead of adding a push-down (LIFO) store to a finite-state control, we add a queue (FIFO) store. Such an automaton can at any time add a symbol to the head of the queue, or else read and remove a symbol from the end of the queue. One might think that such an automaton -- call it a QA (queue automaton) is equivalent in problem solving power to a PDA, but it is, in fact, equivalent in power to a Turing machine. Prove this fact. (Hint: Imagine the queue as being wrapped around to form a circle.) Problem 2 ~~~~~~~~~ It was shown in class that TMs and NTMs are equivalent for language *recognition*. Sipser on p. 153 mentions that they are also equivalent for *deciding* languages, where he defines an NTM that decides a language as one that recognizes the language and always halts. But we can also use a slightly weaker notion of decision of language L by an NTM N: for every w in L, there is a computation of N that accepts w and no computation that rejects it, and for every w not in L there is a computation of N that rejects w. Modify the equivalence proof for recognition so as to prove that a language L is decidable by a TM if and only if it is decidable by an NTM (in the weakened sense of decision by an NTM). Problem 3 ~~~~~~~~~ Define a "monotonic" enumerator for L as one that outputs strings of L in order of length, and prints $ whenever for a given length, there are no strings in L of that length. Assume that $ is not a symbol of the language enumerated, and is distinct from the separator symbol # used to separate output strings. Prove that a monotonic enumerator exists for language L if and only if L is decidable. PROBLEM 4 ~~~~~~~~~ Design a TM (as state diagram) that converts any binary input string w of even length to the form u#v where |u|=|v| and uv=w, and rejects any string of odd length. Thus this machine can serve as a "preprocessor" for another TM that recognizes {w#w | w is a binary string}, so that in combination the two machines recognize {ww | w is a binary string}. The simpler your TM the better. PROBLEM 5 ~~~~~~~~~ Design a TM for {v#w | v,w are nonempty binary strings where v as a binary number is less than w as a binary number} Assume that leading 0's are allowed. PROBLEM 6 ~~~~~~~~~ Design a TM with input alphabet = {1}, that determines whether a given sequence of 1's contains a number of 1's that is a power of 2. The machine should operate by repeatedly deleting (in some sense) every other remaining 1, always making sure that in any one "pass", the number of 1's deleted is the same as the number remaining, till just one 1 is left. PROBLEM 7 ~~~~~~~~~ The following is a TM specification in tabular form. The start state is q, the accept state is q", the input alphabet is {0,1}, and the tape alphabet is {0,1,x,-}, where `-' is the blank-square symbol. state | q | q' | q" | symbol | | | accept | ----------|---------|---------|---------| Where no transitions are 0 | q, 0, R | q, x, R | | shown for q', assume that ----------|---------|---------|---------| there is a transition to 1 | q',x, L | | | a reject state. ----------|---------|---------|---------| x | q, x, R | q',x, L | | ----------|---------|---------|---------| - | q",-, L | | | ----------------------------------------- a. Draw the transition diagram for the TM (omitting the implicit reject state). b. Does the TM always halt? Carefully justify your answer. c. Say as concisely as you can what language the TM recognizes. d. Prove your claim in (c) by two inductions, one for the case where the input to the TM is in the language it recognizes, and one for the case where the input is not in that language. Suggestion: Use induction on the number of times around the loop from state q to state q' and back to state q. For each time around the loop, argue that a property relating the 0's and 1's on the tape (essentially the one expressed in (c)) is maintained. Also you need to consider initial and ultimate conditions.