Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
1.1INTRODUCTION
1.1.1
Statemachines
Astatemachineisamathematicalcomputationmodelbasedonatableoftransitions
betweenindividualstatesundercertainconditions.Thetablecanalsoincludetheoutput
valuesofthestatemachine.Thegeneralclassificationdistinguishesbetweennondetermin-
isticanddeterministicstatemachines,ofwhichonlythelatterareusedhere.Thismeans
thatthetransitionfromthecurrentstatetothenextoneispreciselydefinedandalways
unambiguous.
Considerationsregardingspecificstatemachinesshouldbeprecededbyanotation
andgraphicrepresentationofstatemachines.Thesemachinesarerepresentedasdirected
graphs(Fig.1.1),whereanoderepresentsasinglestate(thenameorsymbolofthestate
iswritteninsidethenode).Incontrast,anedgerepresentsapossibletransitionbetween
states(thenameofthetransitionconditionortheconditionitselfwrittenasalogical
expressionshouldbeshownonedge).Forexample,suchaconditioncouldmean"the
presencesensordetectsanitem".Itisworthnotingthatedgesaredirected,sotransitions
areunidirectional.Thisnotationisnotfullyconsistentwiththeacceptedstandard.Usu-
ally,adoublelinerepresentsanacceptingstateinastatemachine,whilehere,itisused
todenotetheinitialstateofthemachineinsteadofthestandardarrowleadingtothe
firststatebutnothavingasourcestate.Thisnotationiseasiertounderstand.Inthecase
ofmultipletransitionsbetweenstates(oftenintersecting),singlearrowswithoutasource
aremoredifficulttoidentifythancircleswithadoubleline.
Dependingonthetypeofmachineused,theinformationregardingthesetofoutput
signalsmaybelocatednexttothestatename(andsignificantlybelowit)ornextto
thetransitioncondition(oftenalsobelowit).However,usually,onlythosesignalswhose
valuechangesarewrittenthere.Inpractice,outputsareusuallydenotedbysymbols,
whereeachsymbolislaterdescribedseparately.Insimpleprojects,statesareusually
numberedwithconsecutiveintegernumbers.Atthesametime,specificinputsignals(or
theirlogicalcombination)andvaluesofchangingoutputsignalsarewritteninsteadof
transitionandoutputstatesymbols.Crucially,theexamplemachinesshowninFig.1.1
donothavetobeequivalenttoeachother,i.e.,theydonotdescribethesamebehavior.
Hence,thedifferentnamesforthecombinationofoutputsignals.
Q2
Q4
S2
c42
S4
c21
Q1
S1
c52
c13
c31
S3
Q3
S5
Q5
c53
c42/Q42
S2
S4
c21/Q21
c52/Q52
S1
c13/Q13
c31/Q31
S3
S5
c53/Q53
Fig.1.1:AnexamplegraphicalrepresentationofMoore(left)andMealy(right)machines;
thesemachinesarenotequivalent
11
