Mașina cu stări finite (FSM) este un model de proiectare software în care un model dat trece la alte stări comportamentale prin intrare externă.

Înțelegerea mașinii de stat finit

Un FSM este definit prin stări, este stare initiala si tranziții.

Puterea FSM vine din capacitatea de a defini clar diferitele comportamente în diferite condiții. De obicei, FSM este utilizat cu scripturi comportamentale de buclă care evaluează în mod constant situația curentă într-o buclă sau cu evenimente.

Pentru a ajuta la formarea unei imagini a modului în care ar putea fi aplicat acest lucru, o mașină de cafea va fi folosită ca exemplu de mașină cu stare finită. De asemenea, vom acoperi o diagramă de stare pentru a vizualiza FSM și a oferi exemple de codare.

Diagrama de stat

Schema mașinii de cafea cu stare finită
Citește mai multCum se face o promisiune dintr-o funcție de apel invers în JavaScript

Această diagramă prezintă trei stări posibile pentru aparatul de cafea:

  • Deschis
  • ReadyToBuy
  • PoweredOff

Liniile dintre aceste stări arată ce tranziții sunt posibile între stări și în ce direcție. Aceste tranziții au condiții pentru când FSM trebuie să se schimbe între state.

  • StartUpMachine De la starea PoweredOff la starea Open, aparatul trebuie să pornească. Acest lucru se face manual în acest caz.
  • depunere> = costul cafelei FSM evaluează suma de numerar depusă fie într-o buclă, fie când suma se modifică (recomandat în acest caz) Dacă depuneți suficient numerar în aparatul de cafea, FSM va trece de la „Deschis” la „ReadyToBuy” ‘.
  • ShutdownMachine Aparatul va trece automat de la Open la PoweredOff prin metoda ShutDownMachine dacă se îndeplinește condiția „nu mai sunt cafele rămase”.
  • DispenseCoffee În starea ReadyToBuy, utilizatorul poate cumpăra o cafea după care va fi preparată și distribuită. Condiția este când evenimentul BuyCoffee (! Link către modelul de observator!) Se declanșează. (nu este prezentat în diagramă)
  • CancelCoffee Dacă utilizatorul alege să anuleze, aparatul va trece de la ReadyToBuy la Open.
  • ShutDownMachine Mașina va trece la starea PoweredOff

State

În fiecare stare există un comportament definit care va fi executat numai atunci când obiectul se află în acea stare. De exemplu, în timpul PoweredOff aparatul de cafea nu va prepara cafea înainte de a fi pornit, în timpul stării Open va aștepta fie până când este introdus suficient numerar, până când este dată comanda de oprire, sau până când rămâne fără cafea. În timpul acestei stări Deschise poate face rutine precum curățarea care nu se va întâmpla în alte state.

Stare initiala

Fiecare FSM are o stare inițială, aceasta înseamnă în ce stare începe când este creat și trebuie definit atunci când este construit sau instanțiat. Desigur, este posibil să schimbați direct starea dacă sunt îndeplinite condițiile.

Tranziții

Fiecare stat evaluează în mod constant dacă ar trebui să treacă la o altă stare sau va trece la o altă stare pe baza unui eveniment declanșat.

DFA și NFA

Citește mai multCum se generează un fișier de reducere GitHub din Microsoft Word utilizând TypeScript

Există două tipuri de automat finit, Deterministic (DFA) și Nedeterministic (NFA). Ambele acceptă limbi regulate și funcționează mai mult sau mai puțin în același mod descris mai sus, însă cu unele diferențe.

Un DFA acceptă sau respinge un șir de simboluri și produce doar un singur calcul sau automat pentru fiecare șir de intrare. Determinat se referă la unicitatea calculului. O mașină de stat finit se numește DFA dacă respectă următoarele reguli:

  1. Fiecare dintre tranzițiile sale este unic determinat de starea sa sursă și simbolul de intrare
  2. Citirea unui simbol de intrare este necesară pentru fiecare tranziție de stare.

Un NFA nu trebuie să respecte aceste restricții, ceea ce înseamnă că fiecare DFA este, de asemenea, un NFA. Și întrucât ambii recunosc doar limbaje obișnuite, fiecare NFA poate fi convertit într-un DFA echivalent folosind algoritmul de construcție al setului de puteri.

Deci, ce fel de reguli ne putem aștepta să găsim în NFA-uri, dar nu în DFA-uri?

  1. Un NFA poate avea un Șir gol tranziție (în general notată cu un epsilon). Adică, atunci când se află într-o anumită stare cu un epsilon pentru o regulă de tranziție, mașina poate trece la următoarea stare fără a citi un simbol de intrare
  2. Într-un NFA, fiecare pereche de stări și simboluri de tranziție poate avea mai multe stări de destinație, spre deosebire de destinațiile unice ale perechilor din DFA-uri.
  3. Fiecare pereche de stări și simboluri de tranziție produce o „ramură” de calcul pentru fiecare dintre destinațiile sale posibile, creând un fel de sistem cu mai multe fire.
  4. Un DFA va respinge șirul de intrare dacă aterizează în orice alt stat decât cel de acceptare. Într-un NFA, avem nevoie doar de o „ramură” pentru a ateriza într-un stat de acceptare pentru a accepta șirul.

Dacă doriți să aflați mai multe, iată un mare ghid detaliat privind mașinile de stat.