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.