Véges állapotú gép magyarázata

A véges állapotú gép (FSM) egy szoftver tervezési minta, ahol egy adott modell külső bemeneten keresztül más viselkedési állapotokba lép át.

A véges állapotú gép megértése

Az MSZÁ-t állapota , kezdeti állapota és átmenete határozza meg .

Az MSZÁ ereje abból adódik, hogy világosan meghatározhatjuk a különböző viselkedéseket különböző körülmények között. Az MSZÁ-t általában looping viselkedési szkriptekkel használják, amelyek folyamatosan értékelik az aktuális helyzetet egy ciklusban vagy eseményekkel.

Hogy képet alkosson arról, hogyan lehet ezt alkalmazni, egy kávéfőzőt használnak a véges állapotú gép példájára. Ezenkívül áttekintünk egy állapotdiagramot az FSM megjelenítésére és kódolási példákkal.

Államdiagram

Kávéfőző véges állapotú gép diagramja

Ez a diagram a kávéfőző három lehetséges állapotát mutatja:

  • Nyisd ki
  • ReadyToBuy
  • PoweredOff

Az ezen állapotok közötti vonalak megmutatják, hogy az államok között mely átmenetek és milyen irányban lehetségesek. Ezeknek az átmeneteknek megvannak a feltételeik arra, hogy mikor kell az MSZÁ-nak váltani az államok között.

  • StartUpMachine A gépnek be kell indulnia a PoweredOff állapotból az Open állapotba. Ez ebben az esetben manuálisan történik.
  • kaució> = kávé költsége Az MSZÁ vagy hurokban, vagy az összeg változásakor értékeli a letétbe helyezett készpénz mennyiségét (ebben az esetben ajánlott). Ha elegendő készpénzt helyez el a kávéfőzőbe, az FMV „Megnyitás” -ról „Kész” -re vált. ”.
  • ShutdownMachine A gép automatikusan az Open-ből a PoweredOff-ba vált, a ShutDownMachine módszerrel, ha a "nincs több kávé" feltétel teljesül.
  • DispenseCoffee A ReadyToBuy állapotban a felhasználó vásárolhat egy kávét, majd azt főzik és adagolják. Ennek feltétele, hogy a BuyCoffee esemény (! Link a megfigyelő mintához!) Elindul. (a diagramon nem látható)
  • CancelCoffee Ha a felhasználó a lemondás mellett dönt, a gép a ReadyToBuy-ról az Open-re vált.
  • ShutDownMachine A gép PoweredOff állapotba kerül

Államok

Minden állapotban van meghatározott viselkedés, amelyet csak akkor hajtanak végre, ha az objektum ebben az állapotban van. Például a PoweredOff alatt a kávéfőző nem főz kávét a bekapcsolás előtt, a Nyitott állapotban vagy addig vár, amíg elegendő készpénz van behelyezve, amíg a kikapcsolási parancsot meg nem adják, vagy amíg elfogy a kávé. Ebben a nyitott állapotban olyan rutinokat végezhet, mint például a takarítás, amelyek más államokban nem történnek meg.

Kezdeti állapot

Minden MSZÁ-nak van egy kezdeti állapota, ez azt jelenti, melyik állapotban kezdődik, amikor létrehozzák, és meg kell határozni, amikor felépül vagy példányos. Természetesen lehetséges az állapot közvetlen megváltoztatása, ha a feltételek teljesülnek.

Átmenetek

Minden állam vagy folyamatosan értékeli, hogy át kell-e állnia egy másik állapotba, vagy egy kivált esemény alapján áttér egy másik állapotra.

DFA és NFA

Kétféle véges automata létezik, a determinisztikus (DFA) és a nemdeterminisztikus (NFA). Mindkettő elfogadja a rendszeres nyelveket, és többé-kevésbé ugyanúgy működik, mint fent, de némi különbséggel.

A DFA elfogad vagy elutasít egy szimbólumsort, és csak egy egyedi számítást vagy automatát állít elő minden bemeneti karakterlánchoz. A determinisztikus a számítás egyediségére utal. A véges állapotú gépet akkor hívjuk DFA-nak, ha betartja a következő szabályokat:

  1. Minden átmenetét egyedileg határozza meg a forrás állapota és a bemeneti szimbólum
  2. Minden állapotátmenethez bemeneti szimbólum olvasása szükséges.

Az NFA-nak nem kell betartania ezeket a korlátozásokat, vagyis minden egyes DFA egyben NFA is. És mivel mindketten csak a szokásos nyelveket ismerik fel, az egyes NFA-k a PowerSet algoritmus segítségével átalakíthatók egyenértékű DFA-kká.

Tehát milyen szabályokra számíthatunk az NFA-ban, de nem a DFA-ban?

  1. Az NFA-nak lehet üres karakterlánc- átmenete (általában epsilonnal jelölve). Ez azt jelenti, hogy amikor egy átmeneti szabály esetén egy adott állapotban van egy epsilon, a gép bemeneti szimbólum olvasása nélkül átállhat a következő állapotba
  2. Egy NFA-ban minden állapot- és átmeneti szimbólumpárnak több célállapota is lehet, szemben a párok egyedi rendeltetési helyeivel a DFA-ban
  3. Minden állapot- és átmenetszimbólum-pár számítási ágat hoz létre minden lehetséges rendeltetési helyéhez, létrehozva valamiféle többszálas rendszert.
  4. A DFA elutasítja a bemeneti karakterláncot, ha az elfogadás állapotától eltérő állapotba kerül. Egy NFA-ban csak egy „ágra” van szükségünk ahhoz, hogy egy elfogadó állapotba kerüljön a karakterlánc elfogadásához.

Ha többet szeretne megtudni, itt van egy nagyszerű részletes útmutató az állami gépekről.