=========================preview======================
(COMP272)1996_Exam1ver2.pdf
Back to COMP272 Login to download
======================================================
COMP272TheoryofComputation
November29,1996ExamOne

Name: E-mail: StudentNo: Lecture: Tutorial:
.AnswerALLquestions.Theexamisworth300points.
.Timeallowed:80minutes.
1.DFAsandRegularGrammars(70points)
Let
L.fw2fa.bg .:wdoesnotcontainaabasasubstringg:

(a)ConstructaDFAthatacceptsL: (b)ConstructaregulargrammarGthatgeneratesL(i.e.,L(G).L).Recallthata regulargrammarisaspecialformofacontext-freegrammar.
2.NFAsandDFAs(60points)
BuildaDFAthatacceptsthesamelanguageasthatacceptedbythefollowingNFA:
0

2

3.RegularLanguages(90points) Let L.fw2fa.bg .:numberofa-sinw.numberofb-sinwg
IsLregular.Proveyouranswer.Whenprovingyouranswerfullystatethetheorems thatyouareusing(includingtheirassumptionsandtheirconsequences).
3

4.ContextFreeLanguagesandPushdownAutomata(80points) (a)WritedownaContextFreeGrammarthatgeneratesthefollowinglanguage: L.fw2fa.b.cg .:numberofa-sinw.numberofb-sinwg (b)BuildapushdownautomatonthatrecognizesL.Recallthatapushdownautoma-tonisoftheform M.(K...;...s.F) where..thetransitionrelation,isoftheform ..(K....;.).(K.;.): Inthiscase..fa.b.cgandyoumustspecifytheremainingcomponentsofM:
4