周繇
去百度文库,查看完整内容>内容来自用户:好读书不求甚解浙江大3433646430学2017-2018学年秋冬学期《计算理论》课程期末考试试卷课程号:21120520开课学院:计算机学院考试试卷:A卷B卷考试形式:闭卷开卷,允许带入场考试日期:2018年1月24日,考试时间:120分钟诚信考试,沉着应考,杜绝违纪考生姓名学号所属院系题序123456总分得分评卷人ZhejiangUniversityTheoryofComputation,Fall-Winter2017FinalExam1.(24pts)alse.IfitistruefillaTotherwiseaFinthebracketbeforethestatement.(a)()LetA,Bbetwolanguages.IfbothAandA∪Bareregular,thenBisdefinitelyregular.(b)()IfAisregularandBisnon-regular,thenA◦Bmustbenon-regular.(c)()Language{xcyx,y∈{a,b∗,x≤y≤3xiscontext-free.(d)()Everyregularlanguagecanbegeneratedbyacontext-freegrammar.(e)()IfAisrecursiveandB⊆A,thenBisrecursiveaswell.(f)()Recursivelyenumerablelanguagesarealwaysinfinite.(g)()There’safunctionφsuchthatφcanbecomputedbysomeTuringmachines,yetφisnotaprimitiverecursivefunction.(h)()LetAandBberecursivelyenumerablelanguagesandA∩B=∅.IfA∪B