=========================preview======================
(COMP272)[2011](s)final~=4e822^_79368.pdf
Back to COMP272 Login to download
======================================================
COMP 272: Theory of Computation
Spring 2011 Final Exam

1.
Printyour name and studentID at the top of everypage(in case the staplefalls out!).

2.
This is an open-book, open-notes, open-brain exam.

3.
Time limit: 180 minutes.

4.
You should answer all the questions on the exam. At least you should read all the questions. Dontbeintimidatedbythelengthoftheproblem itsnotproportional to its di.culty :)

5.
When asked to describe a Turing machine, you can use either pseudocode or plain language,justlikehowyou would describe an algorithm. You may assume the most convenient variant of the TM, unless you are explicitly told otherwise.

6.
Problems marked with . may be di.cult. Manage your time wisely.

7.
You can write on the back of the paper if you run out of space. Please let us know if you need more scratch paper.

8.
Now, take a deep breath.


1. (14pts)AssumingP = NP and NP .coNP,place the following languages into the correct places in the diagram below.
(a)
H = {Mw : Turing machine M halts on input string w}.

(b)
H.

(c)
{a}
nbn


(d)
{a: n 0}.
nbnn


(e)
{ac: n 0}.


(f)
{ : is a Boolean formula that is satis.able}.

(g)
{ : is a Boolean formula that is not satis.able}.




2. (14 pts)For any class of languages C, de.ne coC = {L | L C}. Mark true, false, or unknown for each of the statementsbelow. Youdo not need tojustifyyour answers.
(a)
Regular = coRegular.

(b)
CFL = coCFL.



(c) P = coP.

(d)
NP = coNP.

(e)
NPC = coNPC.


(f)
Recursive = coRecursive.

(g)
R.E. = coR.E.



3. (12pts)Design a standard(i.e.,deterministic, one-tape) Turing machinetoperformthe

nm
.
..
. .
..
.

following task: Initially on the tape is .. 1... 1. 1... 1. where n m. Compute n . m
n.m

such that .nally on the tape is .. 1... 1..
(a)
(6 pts)Describe informally how the Turing machine works.

(b)
(6 pts) Give a formal de.nition of the Turing machine. You may either use the graphical notation of Turing machines or give the de.nition in the form of M = (K,,,s,H).


4. (10 pts)Adding more tapes to a Turing machine does not increase its computing power, butitturns outthat adding more stacksto apushdownautomatondoes. Infact, aslong astherearetwostacks, apushdownautomatoncanbeused tosimulateaTuring machine. Please .ll the missing pieces of the proof below.
Proof: De.ne a deterministic pushdown automaton with two stacks as M =(K,,,s,H), where K is a .nite set of states, is an alphabet, s K is the initial state, H . K is the set of halting states, and : K . . K . . is the transition function. The con.guration of M is a triple(p,,) K . ., where p is the current state, and and are the contents of the two stacks, read top-down. For convenience, we assumethattheinputisgiveninthesecond stack(thereisnoinputtape), an