állapotgép

Az állapotgép olyan absztrakt modell, amely egy rendszer viselkedését állapotok és az állapotok közötti átmenetek leírásával írja le. A modell véges számú állapotból áll, rendelkezik bemeneti alfabetummal, átmeneti függvénnyel, kezdő állapottal és elfogadó állapotok halmazával.

Formálisan egy állapotgép átmenetfüggvénye meghatározza, hogy adott állapotban és adott bemeneti szimbólumnál melyik legyen a következő állapot. A modell gyakorlati megvalósítása lehet determinisztikus (DFA) vagy nem-determinisztikus (NFA). DFA esetén egy adott állapotban és egy bemeneti szimbólumnál legfeljebb egy átmenet létezik; NFA esetén többféle átmenet is előfordulhat, és a bemeneti szó elfogadásához létezik olyan út, amely végig elfogadó állapotba vezet.

Kimenetük szerint az állapotgépeket kiszolgáló típusokra is bonthatók: Mealy- és Moore-állapotgépek. A Mealy-gép a kimenetet az átmenethez rendeli, míg a Moore-gép a kimenetet az aktuális állapothoz köti. Ezek a különbségek a digitális áramkörök és a szoftveres implementációk tervezésekor fontosak.

Példa egy egyszerű DFA-ra: legyen két állapotunk, q0 (kezdő és elfogadó) és q1. A bemeneti szó bitjei között a 1-esek száma páros legyen az elfogadás feltétele. Olvasás közben a számosságot váltó átmenetek segítségével a gép eldönti, hogy végül elfogadja-e a bemenetet.

Alkalmazások közé tartozik a szöveg- és tokenazonosítás (lexikális elemzés), protokollok és digitális áramkörök modellezése, valamint a nyelvtanok és grammatikák szemléltetése a számítógépes elméletben. Az állapotgépek alapvető eszközök a formális nyelvek és elméleti számítástechnika területén.