Finite State Machine forklaret

Finite state machine (FSM) er et softwaredesignmønster, hvor en given model overgår til andre adfærdsmæssige tilstande via eksternt input.

Forståelse af Finite State Machine

En FSM defineres af dens tilstande , dens oprindelige tilstand og overgange .

Styrken ved FSM kommer fra evnen til klart at definere forskellige adfærd under forskellige forhold. Normalt bruges FSM med looping adfærdsmæssige scripts, der konstant vurderer den aktuelle situation i en loop eller med begivenheder.

For at hjælpe med at danne et billede af, hvordan dette kan anvendes, bliver en kaffemaskine brugt som et eksempel på en finite state-maskine. Vi vil også dække et tilstandsdiagram for at visualisere FSM og give eksempler på kodning.

Stat Diagram

Kaffemaskine finite state maskindiagram

Dette diagram viser tre mulige tilstande for kaffemaskinen:

  • Åben
  • Klar til køb
  • PoweredOff

Linjerne mellem disse tilstande viser, hvilke overgange der er mulige mellem tilstande og i hvilken retning. Disse overgange har betingelser for, hvornår FSM skal skifte mellem stater.

  • StartUpMachine Fra tilstanden PoweredOff til Open skal maskinen starte. Dette gøres manuelt i dette tilfælde.
  • depositum> = kaffeomkostninger FSM evaluerer mængden af ​​deponerede kontanter enten i en løkke, eller når mængden ændres (anbefales i dette tilfælde) Hvis du deponerer nok kontanter i kaffemaskinen, går FSM fra 'Åbn' til 'ReadyToBuy '.
  • ShutdownMachine Maskinen går automatisk fra Open til PoweredOff gennem ShutDownMachine-metoden, hvis betingelsen 'ikke mere kaffe tilbage' er opfyldt.
  • DispenseCoffee I tilstanden ReadyToBuy kan brugeren købe en kaffe, hvorefter den brygges og udleveres. Betingelsen er, når BuyCoffee-begivenheden (! Link til observatørmønster!) Udløses. (ikke vist i diagrammet)
  • CancelCoffee Hvis brugeren vælger at annullere, går maskinen fra ReadyToBuy til Open.
  • ShutDownMachine Maskinen skifter til tilstanden PoweredOff

Stater

I hver tilstand er der defineret adfærd, som kun udføres, når objektet er i denne tilstand. For eksempel, under PoweredOff brygger kaffemaskinen ikke kaffe, før den tændes, i åben tilstand venter den enten, indtil der er indsat nok kontanter, indtil kommandoen til nedlukning er givet, eller indtil den løber tør for kaffe. Under denne åbne tilstand kan den udføre rutiner som rengøring, som ikke sker i andre stater.

Oprindelig tilstand

Hver FSM har en indledende tilstand, det betyder hvilken tilstand den starter i når den oprettes og skal defineres, når den konstrueres eller instantieres. Naturligvis er det muligt at ændre tilstand direkte, hvis betingelserne er opfyldt.

Overgange

Enhver stat evaluerer enten konstant, om den skal overgå til en anden stat eller vil overgå til en anden stat baseret på en udløst begivenhed.

DFA og NFA

Der er to typer af finite automaton, Deterministic (DFA) og Nondeterministic (NFA). Begge accepterer almindelige sprog og fungerer mere eller mindre på samme måde som beskrevet ovenfor, dog med nogle forskelle.

En DFA accepterer eller afviser en streng af symboler og producerer kun en unik beregning eller automat for hver inputstreng. Deterministisk refererer til det unikke ved beregningen. En Finite State Machine kaldes en DFA, hvis den overholder følgende regler:

  1. Hver af dens overgange bestemmes entydigt af dens kildetilstand og input-symbol
  2. Læsning af et input-symbol er påkrævet for hver tilstandsovergang.

En NFA behøver ikke at overholde disse begrænsninger, hvilket betyder, at hver DFA også er en NFA. Og da de begge kun genkender almindelige sprog, kan hver NFA konverteres til en ækvivalent DFA ved hjælp af powerset-konstruktionsalgoritmen.

Så hvilken slags regler kan vi forvente at finde i NFA'er, men ikke DFA'er?

  1. En NFA kan have en tom strengovergang (generelt betegnet med en epsilon). Det betyder, at når maskinen er i en bestemt tilstand med en epsilon til en overgangsregel, kan den overgå til den næste tilstand uden at læse et indgangssymbol
  2. I en NFA kan hvert par af tilstands- og overgangssymboler have flere destinationstilstande i modsætning til de unikke destinationer for par i DFA'er
  3. Hvert par tilstands- og overgangssymboler producerer en 'gren' af beregning for hver af dens mulige destinationer, hvilket skaber en slags et multitrådet system.
  4. En DFA afviser inputstrengen, hvis den lander i en anden tilstand end acceptstatus. I en NFA har vi kun brug for en 'filial' for at lande i en acceptstatus for at acceptere strengen.

Hvis du vil lære mere, er her en god dybdegående guide til statsmaskiner.