计算理论-图灵机课件.ppt

《计算理论-图灵机课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、TheoryofComputationAutomatatheoryandformallanguagesYouliQuBeijingJiaotongUniversityWhatisautomatatheoryAutomatatheoryisthestudyofabstractcomputationaldevicesAbstractdevicesare(simplified)modelsofrealcomputationsComputationshappeneverywhere:Onyourlaptop,onyourcellphone,innature,…Whydoweneedabs

2、tractmodels?AsimplecomputerBATTERYSWITCHinput:switchoutput:lightbulbactions:flipswitchstates:on,offAsimple“computer”BATTERYSWITCHoffonstartffinput:switchoutput:lightbulbactions:ffor“flipswitch”states:on,offbulbisonifandonlyiftherewasanoddnumberofflipsAnother“computer”BATTERYoffoffstart1inputs:

3、switches1and2actions:1for“flipswitch1”actions:2for“flipswitch2”states:on,offbulbisonifandonlyifbothswitcheswereflippedanoddnumberoftimes121offon112222AdesignproblemCanyoudesignacircuitwherethelightisonifandonlyifalltheswitcheswereflippedexactlythesamenumberoftimes?4BATTERY1235?AdesignproblemSu

4、chdevicesaredifficulttoreasonabout,becausetheycanbedesignedinaninfinitenumberofwaysByrepresentingthemasabstractcomputationaldevices,orautomata,wewilllearnhowtoanswersuchquestionsThesedevicescanmodelmanythingsTheycandescribetheoperationofany“smallcomputer”,likethecontrolcomponentofanalarmclocko

5、ramicrowaveTheyarealsousedinlexicalanalyzerstorecognizewellformedexpressionsinprogramminglanguages:ab1isalegalnameofavariableinC5u=isnotDifferentkindsofautomataThiswasonlyoneexampleofacomputationaldevice,andthereareothersWewilllookatdifferentdevices,andlookatthefollowingquestions:Whatcanagiven

6、typeofdevicecompute,andwhatareitslimitations?Isonetypeofdevicemorepowerfulthananother?SomedeviceswewillseefiniteautomataDeviceswithafiniteamountofmemory.Usedtomodel“small”computers.push-downautomataDeviceswithinfinitememorythatcanbeaccessedinarestrictedway.Usedtomodelparsers,etc.TuringMachine

7、sDeviceswithinfinitememory.Usedtomodelanycomputer.time-boundedTuringMachinesInfinitememory,butboundedrunningtime.Usedtomodelanycomputerprogramthatrunsina“reasonable”amountoftime.SomehighlightsofthecourseFiniteautomataWewillunderstandwha