资源描述:
《计算理论导论(英文版)正则语言ppt课件.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、Chapter1FiniteAutomata1MotivationThetheoryofcomputationbeginswithaquestion:Whatisacomputer?Itishardtosetupamanageablemathematicaltheoryofthemdirectly.Itisoftenusefulwhendevelopingknowledgeinanewfieldtostartbyconsideringrestrictedcasesandthengraduallyexpandtothegeneralcase.Suchanapproachallowsag
2、radualincreaseinthecomplexityoftheargumentation.2MotivationInparticular,itisaquitecommonstrategyintheinvestigationofinfinitesystemstostartbyconsideringfinitesubsystems.Forinstance,incompilers(i.e.,inprogramsthattranslateprogramswritteninhigh-levellanguagestoequivalentprogramswritteninmachinelan
3、guages)thelexicalanalyzersarebasicallydesignedasfinite-memoryprograms.Themaintaskofalexicalanalyzeristoscanthegiveninputsandlocatethesymbolsthatbelongtoeachofthetokens.3Centraltotheinvestigationoffinite-memoryprogramsistheobservationthatthesetofallthestatesreachableinthecomputationsofeachsuchpr
4、ogramisfinite.Asaresult,thecomputationsofeachfinite-memoryprogramcanbecharacterizedbyafinitesetofstatesandafinitesetofrulesfortransitionsbetweenthosestates.ModelsofcomputationdevicesforacceptingandgeneratinglanguagesFiniteautomataorfinite-statemachine45theregularoperationsLetAandBlanguages.Wede
5、finetheregularoperationsunion,concatenation,andstarasfollows.TheemptystringisalwaysamemberofA*.6additionalexampleExampleConsiderthelanguagesL1={,0,1}andL2={01,11}.TheunionoftheselanguagesisL1L2={,0,1,01,11},theirconcatenationisL1L2={01,11,001,011,101,111}.L1*={,0,1,01,10,001,100,….}ØL=Ø,an
6、d{}L=LforeachlanguageL.7closedAcollectionofobjectsisclosedundersomeoperationifapplyingthatoperationtomembersofthecollectionreturnsanobjectstillinthecollection.N={1,2,3…}isclosedundermultiplication,notclosedunderdivision.Thesetofintegers(positive,negative,andzero)isclosedundersubtraction.8finit
7、eautomataInputstring-Inputtape,dividedintocells(orcalledsquares),whichcaneachholdexactlyonesymbol.Readingheadmoveslefttoright,onesquareatatime.Initially:leftmostsquareInitialstateStatetranslateCurrentstate&symbolreadWindupinoneofF