állapotgépdarabokat

Az állapotgépdarabok kifejezés az állapotgép (finite state machine, FSM) komponenseire utal. Az állapotgép egy olyan modell, amely adott bemeneti szó alapján egy sor állapot között mozog, meghatározva a viselkedést vagy a felismerést. A modell tipikus darabjai: az állapotok halmaza, a bemeneti ábécé, az átmeneti függvény, a kezdőállapot és az elfogadó állapotok. Bizonyos típusoknál létezik kimenet is, amely az aktuális állapottól vagy az állapot és a bemenet együttesétől függ.

Az állapotgépdarabokat formálisan gyakran így írják fel: G = (Q, Σ, δ, q0, F) egy determinisztikus gép (DFA), ahol Q a állapotok halmaza, Σ a bemeneti ábécé, δ a átmeneti függvény, q0 a kezdőállapot, F pedig az elfogadó állapotok halmaza. Ha kimenet is van, Moore- vagy Mealy-gépről beszélünk: Moore-gép esetén a kimenet λ: Q → Γ, Mealy-gép esetén pedig λ: Q × Σ → Γ. Nem determinisztikus gépeknél (NFA) egyes állapot-bemenet párokhoz több vagy nincs átmenet rendelhető.

Egyes állapotgépdarabok közé tartozik az állapotok reprezentációja (pl. állapotdiagram vagy táblázat), az átmeneti függvény pontos definiálása, a kezdőállapot kijelölése és az elfogadó állapotok meghatározása. Ezek a darabok együtt határozzák meg a gép viselkedését és a felismerhető vagy generálható nyelvet. A gyakorlatban állapotgépeket széles körben alkalmaznak szövegfeldolgozásban, protocol- és vezérlőrendszerekben, illetve nyelvi és mintafelismerési feladatokban.