Objašnjeni stroj konačnog stanja

Stroj s konačnim stanjima (FSM) je obrazac softverskog dizajna gdje zadani model prelazi u druga stanja ponašanja putem vanjskog unosa.

Razumijevanje konačnog državnog stroja

FSM je definiran svojim stanjima , početnim stanjem i prijelazima .

Moć FSM-a dolazi iz sposobnosti da se jasno definiraju različita ponašanja u različitim uvjetima. Obično se FSM koristi s petljama skripti za ponašanje koje neprestano procjenjuju trenutnu situaciju u petlji ili s događajima.

Da bi se stvorila slika kako se to može primijeniti, aparat za kavu koristit će se kao primjer automata s konačnim stanjima. Također ćemo pokriti dijagram stanja za vizualizaciju FSM-a i pružiti primjere kodiranja.

Dijagram stanja

Dijagram automata za kavu s konačnim stanjem

Ovaj dijagram prikazuje tri moguća stanja aparata za kavu:

  • Otvoren
  • ReadyToBuy
  • PoweredOff

Linije između tih stanja pokazuju koji su prijelazi mogući između država i u kojem smjeru. Ti prijelazi imaju uvjete kada se FSM treba mijenjati između država.

  • StartUpMachine Iz stanja PoweredOff u stanje Open, stroj se mora pokrenuti. U ovom se slučaju to radi ručno.
  • polog> = trošak kave FSM procjenjuje iznos položene gotovine bilo u petlji ili kada se iznos mijenja (preporučeno u ovom slučaju) Ako položite dovoljno gotovine u aparat za kavu, FSM će prijeći s "Otvoreno" na "ReadyToBuy '.
  • ShutdownMachine Stroj će automatski prijeći s Open na PoweredOff metodom ShutDownMachine ako je zadovoljen uvjet "nema više kave".
  • DispenseCoffee U stanju ReadyToBuy korisnik može kupiti kavu nakon čega će se skuhati i točiti. Uvjet je kada se aktivira događaj BuyCoffee (! Veza na obrazac promatrača!). (nije prikazano na dijagramu)
  • CancelCoffee Ako se korisnik odluči otkazati, uređaj će prijeći iz ReadyToBuy u Open.
  • ShutDownMachine Stroj će preći u stanje PoweredOff

Države

U svakom stanju postoji definirano ponašanje koje će se izvršiti samo kada je objekt u tom stanju. Na primjer, tijekom PoweredOff aparat za kavu neće kuhati kavu prije nego što se uključi, tijekom stanja Otvoreno pričekat će ili dok se ne ubaci dovoljno gotovine, dok se ne izda naredba za isključivanje ili dok ne ostane bez kave. Tijekom ovog otvorenog stanja može obavljati rutine poput čišćenja što se neće dogoditi u drugim državama.

Početno stanje

Svaki FSM ima početno stanje, to znači u kojem stanju započinje kada je stvoren i mora se definirati kada se konstruira ili instancira. Naravno da je moguće izravno promijeniti stanje ako su ispunjeni uvjeti.

Prijelazi

Svaka država ili stalno procjenjuje treba li prijeći u drugo stanje ili će prijeći u drugo stanje na temelju aktiviranog događaja.

DFA i NFA

Postoje dvije vrste konačnih automata, deterministički (DFA) i nedeterministički (NFA). Oboje prihvaćaju redovite jezike i djeluju manje-više na gore opisani način, ali s određenim razlikama.

DFA prihvaća ili odbija niz simbola i proizvodi samo jedno jedinstveno računanje ili automat za svaki ulazni niz. Determinističko se odnosi na jedinstvenost izračuna. Stroj s konačnim stanjima naziva se DFA ako se pridržava sljedećih pravila:

  1. Svaki od njegovih prijelaza jedinstveno je određen izvornim stanjem i ulaznim simbolom
  2. Očitavanje ulaznog simbola potrebno je za svaki prijelaz stanja.

NFA ne mora poštivati ​​ta ograničenja, što znači da je svaki DFA ujedno i NFA. A budući da obojica prepoznaju samo redovite jezike, svaki se NFA može pretvoriti u ekvivalentni DFA pomoću algoritma izrade powerseta.

Pa kakva pravila možemo očekivati ​​da ćemo naći u NFA-ima, ali ne i u DFA-ima?

  1. NFA može imati prazan prijelaz niza (obično označen epsilonom). To znači da kada je u određenom stanju s epsilonom za pravilo prijelaza, stroj može prijeći u sljedeće stanje bez čitanja ulaznog simbola
  2. U NFA-u svaki par stanja i simbola prijelaza može imati više stanja odredišta za razliku od jedinstvenih odredišta parova u DFA-ima
  3. Svaki par stanja i prijelaznog simbola stvara 'granu' računanja za svako svoje moguće odredište stvarajući neku vrstu višenitnog sustava.
  4. DFA će odbiti ulazni niz ako padne u neko drugo stanje osim u stanje prihvaćanja. U NFA-u trebamo samo jednu 'granu' koja će sletjeti u stanje prihvaćanja kako bismo prihvatili niz.

Ako želite saznati više, evo sjajnog detaljnog vodiča o državnim strojevima.