Állapotátmeneti táblázat - State-transition table
Az automata elméletben és a szekvenciális logikában az állapotátmeneti táblázat olyan táblázat, amely megmutatja, hogy egy végesállapotú gép milyen állapotba (vagy állapotokba kerül egy nemdeterminisztikus véges automata esetén ) az aktuális állapot és egyéb bemenetek alapján. Lényegében egy igazságtábla , amelyben a bemenetek az aktuális állapotot tartalmazzák más bemenetekkel együtt, a kimenetek pedig a következő állapotot tartalmazzák más kimenetekkel együtt.
Az állapotátmeneti táblázat a véges állapotú gép megadásának számos módja. Egyéb módok közé tartozik az állapot diagram .
Gyakori formák
Egydimenziós
Az állapotátmeneti táblák néha egydimenziós táblázatok, más néven jellegzetes táblák . Sokkal inkább hasonlítanak az igazságtáblákhoz, mint a kétdimenziós formájukhoz. Az egyetlen dimenzió jelzi az állapotátmenetekhez kapcsolódó bemeneteket, aktuális állapotokat, következő állapotokat és (opcionálisan) kimeneteket.
| Bemenet | Jelen állapot | Következő állapot | Kimenet |
|---|---|---|---|
| I 1 | S 1 | S i | O x |
| I 2 | S 1 | S j | O y |
| … | … | … | … |
| I n | S 1 | S k | O z |
| I 1 | S 2 | S i ′ | O x ′ |
| I 2 | S 2 | S j ′ | O y ′ |
| … | … | … | … |
| I n | S 2 | S k ′ | O z ′ |
| … | … | … | … |
| I 1 | S m | S i ″ | O x ″ |
| I 2 | S m | S j ″ | O y ″ |
| … | … | … | … |
| I n | S m | S k ″ | O z ″ |
Kétdimenziós
Az állapotátmeneti táblák általában kétdimenziós táblák. Elrendezésüknek két általános módja van.
Az első módon az egyik dimenzió az aktuális állapotokat, míg a másik a bemeneteket jelöli. A sor / oszlop metszéspontok jelzik a következő állapotokat és (opcionálisan) az állapotátmenetekhez társított kimeneteket.
|
Bemenet
Jelen állapot
|
I 1 | I 2 | … | I n |
|---|---|---|---|---|
| S 1 | S i / O x | S j / O y | … | S k / O z |
| S 2 | S i ′ / O x ′ | S j ′ / O y ′ | … | S k ′ / O z ′ |
| … | … | … | … | … |
| S m | S i ″ / O x ″ | S j ″ / O z ″ | … | S k ″ / O z ″ |
A második módon az egyik dimenzió az aktuális állapotokat, míg a másik a következő állapotokat jelöli. A sor / oszlop metszéspontjai jelzik az állapotátmenetekhez kapcsolódó bemeneteket és (opcionálisan) kimeneteket.
|
Következő állapot
Jelen állapot
|
S 1 | S 2 | … | S m |
|---|---|---|---|---|
| S 1 | I i / O x | - | … | - |
| S 2 | - | - | … | I j / O y |
| … | … | … | … | … |
| S m | - | I k / O z | … | - |
Egyéb formák
Több véges állapotú gép egyidejű átmenete megmutatható abban, ami gyakorlatilag egy n-dimenziós állapotátmeneti táblázat, amelyben sorpárok az aktuális állapotokat (halmazokat) leképezik a következő állapotokra. Ez egy alternatíva a különálló, egymástól függő végesállapotú gépek közötti kommunikáció képviseletéhez.
A másik végletben külön táblákat alkalmaztak egyetlen véges állapotú gépen belüli minden átmenethez: az "ÉS / VAGY táblák" hasonlóak a hiányos döntési táblákhoz , amelyekben a jelen szabályokra vonatkozó döntés implicit módon a a kapcsolódó átmenet.
Példa
Az alábbiakban egy példa egy állapot-átmenet táblára és a véges állapotú gép megfelelő állapotdiagramjára található:
|
Bemenet
Jelen állapot
|
0 | 1 |
|---|---|---|
| S 1 | S 2 | S 1 |
| S 2 | S 1 | S 2 |
|
Az állapotátmeneti táblázatban a véges állapotú gép összes lehetséges bemenete a táblázat oszlopaiban, míg az összes lehetséges állapot felsorolásra kerül a sorok között. Ha a gép S 1 állapotban van (az első sor) és 1 értékű bemenetet kap (második oszlop), akkor a gép S 1 állapotban marad . Ha a gép S 1 állapotban van, és 0 bemenetet kap (első oszlop), akkor a gép áttér az S 2 állapotra .
Az állapotdiagramon az előbbit az S 1- től az S 1-ig jelölt, 1-gyel jelölt nyíl, az utóbbit pedig az S 1- től S 2-ig egy 0-val jelölt nyíl jelöli . Ez a folyamat statisztikailag leírható Markov láncok .
Egy nemdeterminisztikus végesállapotú gép esetében egy bemenet miatt a gép több állapotban lehet, ezért annak nem determinizmusa . Ezt egy állapotátmeneti táblázatban az összes célállapot halmaza, amely egy göndör zárójelpárba van zárva {}. Az alábbiakban egy példa egy állapotátmeneti táblára és egy nemdeterminisztikus végesállapotú gép megfelelő állapotdiagramjával együtt található:
|
Bemenet
Jelen állapot
|
0 | 1 |
|---|---|---|
| S 1 | S 2 | S 1 |
| S 2 | {S 1 , S 2 } | S 2 |
|
Ha a gép S 2 állapotban van, és 0 bemenetet kap, akkor a gép egyszerre két állapotban lesz, az S 1 és S 2 állapotokban .
Átalakítások / állapot diagramra
Állapotdiagramot lehet rajzolni egy állapotátmenet táblából. Az alábbiakban a könnyen követhető lépések sorozata található:
- Rajzolja a köröket a megadott állapotok ábrázolására.
- Az egyes államok esetében szkennelje át a megfelelő sort, és húzjon egy nyíl a célállomás (ok) ra. Több nyil lehet egy bemeneti karakterhez, ha a végesállapotú gép nem determinisztikus.
- Jelöljön ki egy állapotot kezdő állapotnak . A kiindulási állapotot a végesállapotú gép formális meghatározása adja.
- Jelöljön egy vagy több állapotot elfogadó állapotnak . Ezt a végesállapotú gép formális meghatározása is megadja.
Lásd még
Hivatkozások
További irodalom
- Michael Sipser: Bevezetés a számítás elméletébe . PWS Publishing Co., Boston 1997 ISBN 0-534-94728-X