计算机专业英语11.4节-Finite-State-Machine

专业英语11.4Finite-StateMachines（有限状态机）编译原理中是有限状态自动机（Finite-StateAutomata）,与有限状态机不同，本节里的Mooremachine与有限状态自动机更接近。Wethinkofamachineasasystemthatcanacceptinput,possiblyproduceoutput,andhavesomesortofinternalmemory(内存)thatcankeeptrackofcertaininformationaboutpreviousinputs.Thecompleteinternalconditionofthemachineandallofitsmemory,atanyparticulartime,issaidtoconstitutethestateofthemachineatthattime.Thestateinwhichamachinefindsitselfatanyinstantsummarizesitsmemoryofpastinputsanddetermineshowitwillreacttosubsequent（随后的）input.Whenmoreinputarrives,thegivenstateofthemachinedetermines(withtheinput)thenextstatetobeoccupied,andanyoutputthatmaybeproduced.Ifthenumberofstatesisfinite,themachineisafinite-statemachine.我们将机器看做这样一个系统，他可以接受输入，也许会产生输出，他还有可以用来记录关于以前输入的信息的内存。在特定时间内，机器的完整内部状态和它的所有内存构成了当时机器的状态。该机器在任意时刻的状态综合了以前输入的信息，并决定了他对下一输入的反应。当还有输入到达时，该机器的给出状态（用该输入）确定了将要处于的下一个状态，以及可能产生的某个输出。如果该机器的状态的数目是有限的，我们就称之为有限状态机。SupposethatwehaveafinitesetS={s0,s1,…,sn},afinitesetI,andforeachx∈I,afunctionfx:S→S.Letζ={fx|x∈I}.Thetriple(S,I,ζ)iscalledafinite-statemachine,Siscalledthestatesetofthemachine,andtheelementsofSarecalledstates.ThesetIiscalledtheinputsetofthemachine.Foranyinputx∈I,thefunctionfxdescribestheeffectthatthisinputhasonthestatesofthemachineandiscalledastatetransitionfunction.Thusifthemachineisinstatesiandinputxoccurs,thenextstateofthemachinewillbefx(si).假设有一个有限集S,有限集I，对每个x属于I，有函数fx，完成S到S的映射。令zeta={fx|x∈I}，三元组(S,I,ζ)就是一个有限状态机，S是状态集，集合S中的元素就是状态，集合I是输入集。函数fx是状态转换函数，与任意输入x属于I，函数fx描述了该输入对机器状态的影响。如果机器处于si状态并有输入x发生，那么机器的下一状态为fx(si)Sincethenextstatefx(si)isuniquelydeterminedbythepair(si,x),thereisafunctionF:S×I→SgivenbyF(si,x)=fx(si)因为当前状态si和输入x可以唯一确定下一状态fx(si),我们可以定义一个函数F完成S乘I到S的映射，F(si,x)=fx(si).TheindividualfunctionsfxcanallberecoveredfromaknowledgeofF.ManyauthorswilluseafunctionF:S×I→S,insteadofaset{fx|x∈I},todefineafinite-statemachine.Thedefinitionsarecompletelyequivalent.Example1.LetS={s0,s1}andI={0,1}.Definef0andf1asfollowsf0(s0)=s0,f1(s0)=s1,f0(s1)=s1,f1(s1)=s0,,Thefinite-statemachinehastwostates,s0ands1,andacceptstwopossibleinputs,0and1.Theinput0leaveseachstatefixed,andtheinput1reversesstates.Wecanthinkofthismachineasamodelforacircuit(oflogical)deviceandvisualizesuchadeviceasinFigure11-1.Theoutputsignalswill,atanygiventime,consistoftwovoltages,onehigherthantheother.Eitherline1willbeatthehighervoltageandline2atthelower,orthereverse.Thefirstsetofoutputconditionswillbedenoteds0andthesecondwillbedenoteds1.Aninputpulse,representedbythesymbol1,willreverseoutputvoltages.Thesymbol0representstheabsenceofaninputpulseandsoresultsinnochangeofoutput.ThisdeviceisoftencalledaTflip-flopandisaconcreterealizationofthemachineinthisexample.该有限状态机有两个状态s0和s1，两个输入0和1。输入0保留每个状态不变，而输入1使状态反转。我们可以将该机器看做一个电路设备模型，如图11-1所示。输出信号在任一特定时间都将由两个电压组成，一个比另一个高。line1在高电压，line2在低电压，或者相反。第一组输出条件记为s0,第二组记为s1。由符号1表示的输入脉冲将反转输出电压。0表示没有输入脉冲，因此不会导致输出的改变。这种设备称之为触发器，是本例中机器的具体实现。WesummarizethismachineinFigure11-2.Thetableshownthereliststhestatesdownthesideandinputsacrossthetop.Thecolumnundereachinputgivesthevaluesofthefunctioncorrespondingtothatinputateachstateshownontheleft.01s0s0s1s1s1s0在图11-2中，表的头部是输入，左边是状态。每个输入下面的列给出了在左边各个状态时对应于那个输入的函数值。InputsignalLine1Line2OutputsignalThearrangmentillustratedinFigure11-2forsummarizingtheeffectofinputsonstatesiscalledthestatetransitiontableofthefinite-statemachine.Itcanbeusedwithanymachineofreasonablesizeandisaconvenientmethodofspecifyingthemachine.这段就是说图11-2这样的图就叫做有限状态机的状态转换表。它可以与任意合理大小的机器一起使用，是一种方便的表现机器含义的方法Example2.ConsiderthestatetransitiontableshowminFigure11-3.Hereaandbarethepossibleinputs,andtherearethreestates,s0,s1,ands2.Thetableshowsusthatfa(s0)=s0,fa(s1)=s2,fa(s2)=s1Andfb(s0)=s1,fb(s1)=s0,fa(s2)=s2这段就是解释图11-3的状态转换图，a和b时输入，s0,s1,s2是三个状态，当机器处于状态s0时，得到输入a,就会转换到状态s0,得到输入b就会转换到状态s1,以此类推。IfMisafinite-statemachinewithstatesS,inputsI,andstatetransitionfunctions{fx|x∈I},wecandeterminearelationRMonSinanaturalway.（状态集S，输入集I，状态转换函数集{fx|x∈I}）Ifsi,sj∈S,wesaythatsiRMsjifthereisaninputxsothatfx(si)=sj.如果M是一个有限状态机，有状态集S，输入集I，和状态转换函数集{fx|x∈I}，我们就可以很自然地确定S上的关系RM。(状态集,输入集,状态转换函数集{fx|x∈})如果si,sj∈S,我们说siRMsj如果有输入x使得fx(si)=sj。ThussiRMsjmeansthatifthemachineisinstatesi,thereissomeinputx∈Ithat,ifreceivednext,willputthemachineinstatesj.therelationRMpermitsustodescribethemachineMasalabeleddigraphoftherelationRMonS,whereeachedgeislabeledbythesetofallinputsthatcausethemachinetochangestatesasindicatedbythatedge.（siRMsj的意思是如果机器M处于状态si,在收到输入x后会转换到状态sj）（关系允许我们把（有限状态）机器M描述为S上关系的加标记的有向图，其中每条边用那样的输入集来标记，即这些输入将引起机器如同由那条边所指示的那样改变状态）Example3.ConsiderthemachineofExample2.Figure11-4showsthedigraphoftherelationRM,witheachedgelabeledappropriately.NoticethattheentirestructureofMcanberecoveredfromthisdigraph,sinceedgesandtheirlabelsindicatewhereeachinputsendseachstate.例3。考虑例2中的机器。图11-4显示了关系RM的有向图，图中每条边都有适当的标记。M的整个结构可以从这个有向图中恢复，因为边及其标签可以显示出每个输入送往哪个状态。abs0s0s1s1s2s0s2s1s2Example4.ConsiderthemachineMwhosestatetableisshowninFigure11-5(a).thedigraphofRMisthenshowninFigure11-5(b),withedgeslabeledappropriately.Notethatanedgemaybelabeledbymorethanoneinput,sinceseveralinputsmaycause