=========================preview======================
(COMP272)1996_Quiz1.pdf
Back to COMP272 Login to download
======================================================
COMP272TheoryofComputation
October2,1996QuizOne
Name: E-mail: StudentNo: Lecture: Tutorial:
.AnswerALLquestions.Youareonlyrequiredtowritedowntheanswers.youdonotneedto justifythem.Inquestions4and5youonlyneedtodrawthestatediagramoftheDFA.youdo notneedtoproveitiscorrect.Donotforgettodenotethestartand.nalstatesproperly.
.Timeallowed:45minutes.
.Theexamisworth150points.Eachquestionisworth30..
itimes
z }| {
1.LetN.f0.1.2.3.:::gbethesetofwholenumbers.Ni.N.N.....N:Foreachof thefollowingsetsdecidewhethertheyarecountableornotcountableandcirclethecorrect answer:
(a)N.N.Ncountableuncountable
(b)2N countableuncountable
(c)[1Nicountableuncountable
i.0
2.Writearegularexpressionrepresentingthefollowinglanguage.Note:0isdivisiblebyboth 2and3:
.
fw2fa.bg:(Numberofa-sinwisdivisibleby2) or(numberofb-sinwisdivisibleby3),orbothg
3.Writearegularexpressionrepresentingthefollowinglanguage:
.
fw2fa.bg:wdoesnotcontainaaag:
1
4.DrawaDFAthatacceptsthelanguage
.
fw2fa.bg:(Numberofa-sinwisoddandnumberofb-siseven) or(Numberofa-sinwisevenandnumberofb-sisodd)g
5.DrawaDFAthatacceptsthelanguage
.
fw2f0.1g:wcontainsthestring01101g:
2