=========================preview======================
(COMP272)1996_Exam2L1.pdf
Back to COMP272 Login to download
======================================================
COMP272TheoryofComputation
Lecture1{Dr.MordecaiGolin

December16,1996FinalExam
.AnswerALLquestions.Theexamisworth400points.
.Timeallowed:180minutes.
.Writeyouranswersinthetestbook.
1.(60pts)Inyourownwordsbrie.yde.nethefollowingterms/symbols(twotothree sentenceseachwillsu.ce).
(a)P:
(b)NP:
(c)TuringDecidableLanguages.
(d)UniversalTuringMachines.

2.(60pts)Let
K0.f.(M):TuringMachineMacceptsinputstring.(M)g
ProvethatK0isnotTuringDecidable.
3.(100pts)Provethetruthorfalsehoodofthefollowingstatements.Inyourproofs completelystatethetheoremsyouareusing(theirassumptionsandconclusions).

(a)IfLisTuringDecidablethen
isTuringAcceptable. (b)TherearelanguagesinPthatarenotinNP: (c)IfLisaContextFreeLanguageandFisa.nitelanguagethen(L;F)isa
ContextFreeLanguage. (d)IfLisnotaContextFreeLanguageandFisa.nitelanguagethen(L;F)is
notaContextFreeLanguage.
4.(60pts)ConstructaTuringMachinethatacceptsthelanguage
L.fuu R:u2fa.bg . g:
Thatis,yourTuringMachineshouldstartincon.guration(s.
wherew2

fa.bg.containsnoblanks,andhaltifandonlyifw2L:Byconstructwemeandraw aTuringmachinebycombiningsmallerTuringmachinesinthefashiondescribedin class.ThesmallerTuringmachinesyoumayuseare
L:Moveleftonesquare
R:MoveRightonesquare L:Moveleftuntila.isfound R:Moverightuntila.isfound
Wor.:Writethecharacter.
(.signi.esanycharacterinfa.bg).Note:u Risthereverseofu:
5.(60pts)Let
.w)2
L.fw2fa.bg:numberofa-sinw.(numberofb-sing
IsLContext-Free.IsLRegular.Proveyouranswer.Whenprovingyouranswer fullystatethetheoremsthatyouareusing(includingtheirassumptionsandtheir conclusions).
6.(60pts)Let
L.fw2fa.b.cg .:thelengthofwisodd andthemiddlesymbolofwisanag
IsLContext-Free.IsLRegular.Proveyouranswer.Whenprovingyouranswer fullystatethetheoremsthatyouareusing(includingtheirassumptionsandtheir conclusions).
2