Tabulka přechodu stavu - State-transition table
V teorii automatů a sekvenční logice je tabulka přechodu stavu tabulka ukazující, do kterého stavu (nebo stavů v případě nedeterministického konečného automatu ) se stroj konečného stavu přesune na základě aktuálního stavu a dalších vstupů. Je to v podstatě pravdivostní tabulka, ve které vstupy zahrnují aktuální stav spolu s dalšími vstupy a výstupy zahrnují další stav spolu s dalšími výstupy.
Tabulka přechodu stavu je jedním z mnoha způsobů, jak určit stroj v konečném stavu. Mezi další způsoby patří stavový diagram .
Běžné formy
Jednorozměrný
Tabulky přechodu stavu jsou někdy jednorozměrné tabulky, nazývané také charakteristické tabulky . Jsou mnohem podobnější tabulkám pravdy než jejich dvojrozměrné formě. Jedna dimenze označuje vstupy, aktuální stavy, další stavy a (volitelně) výstupy spojené s přechody stavu.
Vstup | Aktuální stav | Další stav | Výstup |
---|---|---|---|
Já 1 | S 1 | S i | O x |
I 2 | S 1 | S j | O y |
… | … | … | … |
Já n | S 1 | S k | O z |
Já 1 | S 2 | S i ' | O x ′ |
I 2 | S 2 | S j ' | O y ' |
… | … | … | … |
Já n | S 2 | S k ' | O z ′ |
… | … | … | … |
Já 1 | S m | S i ″ | O x ″ |
I 2 | S m | S j " | O y " |
… | … | … | … |
Já n | S m | S k ″ | O z ″ |
Dvourozměrný
Tabulky přechodu stavu jsou obvykle dvourozměrné tabulky. Existují dva běžné způsoby jejich uspořádání.
Prvním způsobem jedna z dimenzí označuje aktuální stavy, zatímco druhá označuje vstupy. Křižovatky řádek / sloupec označují další stavy a (volitelně) výstupy spojené s přechody stavu.
Vstup
Aktuální stav
|
Já 1 | I 2 | … | Já n |
---|---|---|---|---|
S 1 | S i / O x | S j / O r | … | 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“ |
Druhým způsobem jedna z dimenzí označuje aktuální stavy, zatímco druhá označuje další stavy. Křižovatky řádek / sloupec označují vstupy a (volitelně) výstupy spojené s přechodem stavu.
Další stav
Aktuální stav
|
S 1 | S 2 | … | S m |
---|---|---|---|---|
S 1 | I I / O x | - | … | - |
S 2 | - | - | … | Já j / o y |
… | … | … | … | … |
S m | - | I k / o z | … | - |
Jiné formy
Simultánní přechody ve více strojích s konečným stavem lze zobrazit v efektivně n-dimenzionální tabulce přechodu stavu, ve které dvojice řádků mapují (sady) aktuální stavy na další stavy. Toto je alternativa k reprezentaci komunikace mezi samostatnými, vzájemně závislými stroji s konečným stavem.
Na druhém konci byly použity samostatné tabulky pro každý z přechodů v jediném stroji s konečným stavem: „AND / OR tables“ jsou podobné neúplným rozhodovacím tabulkám, ve kterých je rozhodnutí pro pravidla, která jsou přítomna, implicitně aktivací související přechod.
Příklad
Níže je uveden příklad tabulky přechodu stavu spolu s odpovídajícím stavovým diagramem pro stroj s konečným stavem:
Vstup
Aktuální stav
|
0 | 1 |
---|---|---|
S 1 | S 2 | S 1 |
S 2 | S 1 | S 2 |
V tabulce přechodu stavu jsou všechny možné vstupy do stroje s konečným stavem vyčísleny napříč sloupci tabulky, zatímco všechny možné stavy jsou vyčísleny napříč řádky. Pokud je stroj ve stavu S 1 (první řádek) a obdrží vstup 1 (druhý sloupec), stroj zůstane ve stavu S 1 . Nyní, pokud je stroj ve stavu S 1 a obdrží vstup 0 (první sloupec), stroj přejde do stavu S 2 .
Ve stavovém diagramu je první označena smyčkou šipky od S 1 do S 1 označenou 1 a druhá je označena šipkou od S 1 do S 2 označenou 0. Tento proces lze statisticky popsat pomocí Markovovy řetězy .
U nedeterministického stroje s konečným stavem může vstup způsobit, že je stroj ve více než jednom stavu, a proto je nedeterministický . Toto je v tabulce přechodu stavu označeno množinou všech cílových stavů uzavřených v dvojici složených závorek {}. Níže je uveden příklad tabulky přechodu stavu spolu s odpovídajícím stavovým diagramem pro nedeterministický stroj s konečným stavem:
Vstup
Aktuální stav
|
0 | 1 |
---|---|---|
S 1 | S 2 | S 1 |
S 2 | {S 1 , S 2 } | S 2 |
Pokud je stroj ve stavu S 2 a přijme vstup 0, bude stroj ve dvou stavech současně, ve stavech S 1 a S 2 .
Transformace z / do stavového diagramu
Je možné nakreslit stavový diagram z tabulky přechodu stavu. Níže je uvedena řada snadno sledovatelných kroků:
- Nakreslete kruhy, které představují dané stavy.
- Pro každý ze států naskenujte přes odpovídající řádek a nakreslete šipku do cílového stavu. Pokud je stroj konečného stavu nedeterministický, může být pro vstupní znak více šipek.
- Určete stav jako počáteční stav . Počáteční stav je uveden ve formální definici stroje konečného stavu.
- Určete jeden nebo více stavů jako přijímající stav . To je také uvedeno ve formální definici stroje konečného stavu.
Viz také
Reference
Další čtení
- Michael Sipser: Úvod do teorie výpočtu . PWS Publishing Co., Boston 1997 ISBN 0-534-94728-X