=========================preview======================
(COMP272)1996_Quiz2.pdf
Back to COMP272 Login to download
======================================================
COMP272TheoryofComputation
November21,1996Quiztwo

Name: E-mail: StudentNo: Lecture: Tutorial:
.AnswerALLquestions.
.Timeallowed:45minutes.
.Theexamisworth150points.
1.(a)Thelanguage
b2n
L1.fa nc 3n:n.0g
isnotContext-free.Provethisfact.Inyourprooffullystatethetheoremsthatyouare using(includingtheirassumptionsandtheirconsequences). (b)Let
L2.fw2fa.b.cg .:(Numberofb-sinw).2.(Numberofa-sinw) and(Numberofc-sinw).3.(Numberofa-sinw)g
IsL2Context-free.Proveyouranswer.Whenprovingyouranswer,fullystatethe theoremsthatyouareusing(includingtheirassumptionsandtheirconsequences).
2

2.ConstructtherightshiftingTuringmachineSRthattransforms#w#.wherew2fa.b.cg.

containsnoblanks,into##w#:ByconstructwemeandrawaTuringmachinebycombining

smallerTuringmachinesinthefashiondescribedinclass.ThesmallerTuringmachinesyou mayuseare
L : Move leftonesquare
R : Move Rightonesquare
L : Move leftuntila.isfound
R : Move right u n tila.is found
Wor. : Write thecharacter.

Notethat.signi.esanycharacterinfa.b.c.#g
3