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
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:
- Minden átmenetét egyedileg határozza meg a forrás állapota és a bemeneti szimbólum
- 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?
- 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
- 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
- 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.
- 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.