Az elméleti számítástechnikában az állapotátmeneti rendszer az absztrakt gép egyik formája, amelyet egy vagy több számítás modellezésére használnak .
Az állapotátmeneti rendszer állapotok halmazából és államok közötti átmenetekből áll, amelyek felcímkézhetők; ugyanaz a címke több átmenetnél is megjelenhet. Ha a címkekészlet egyedi , akkor a címkézés elhagyható.
Az állapotátmeneti rendszerek irányított grafikonok .
A felcímkézetlen állapotátmeneti rendszer egy pár , ahol az állapothalmaz és az átmeneti viszony. Ha és két állapot, azt jelenti, hogy van átmenet a- ból , és lejegyezzük .
Nem a priori feltételezés készült és , és lehet végtelen, sőt megszámlálhatatlan.
A címkézett állapotátmeneti rendszer egy hármas , állapotok halmazával, címkekészletével és az átmenet relációval. Ha van egy átmenet, amelyet két állapot között jelöl és és akkor írunk .
Vegye figyelembe, hogy az átmeneti reláció meghatározása nem határozza meg, hogy bináris relációról van-e szó :
Abban az esetben, ha végesek és végesek, véges automatáról (vagy véges állapotú gépről ) beszélünk . Általában megadunk magunknak egy beviteli szó elfogadási feltételt is, amely gyakran az S két részének az adatai lesznek, amelyek a kezdeti és az elfogadó állapotok lesznek.
Az átmeneti rendszerről azt mondják, hogy determinisztikus, ha definíció szerint függvény . A nem determinisztikus átmeneti rendszer kifejezés minden állapotátmeneti rendszert minősít, ha meg kell határoznunk, hogy nem korlátozódunk a determinisztikus rendszerekre.
Az átmeneti rendszerek fontos szerepet játszanak A hivatalos nyelvek felismerésében , különösen azok osztályozásában .
Az ellenőrző modellekben ( angolul : modellellenőrzés ) a rendszerállapot-átmenetek emellett tartalmazzák az állapotok címkézési funkcióját (pl. Kripke-szerkezet ).
A felirat nélküli statechart rendszer egy absztrakt rendszer (en) átírása .