计算理论导论(英文版)正则语言ppt课件.ppt

《计算理论导论(英文版)正则语言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.TheemptystringisalwaysamemberofA*.6additionalexampleExampleConsiderthelanguagesL1={,0,1}andL2={01,11}.TheunionoftheselanguagesisL1L2={,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