Tabulka přechodu stavu - State-transition table

v teorie automatů a sekvenční logika, a tabulka přechodu stavu je tabulka ukazující, jaký stav (nebo stavy v případě a nedeterministický konečný automat ) a konečný stavový stroj se přesune na na základě aktuálního stavu a dalších vstupů. Je to v zásadě a pravdivostní tabulka ve kterém 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ří a 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.

Tabulka přechodu stavu
(S: stav, I: vstup, O: výstup)
Vstup	Aktuální stav	Další stav	Výstup
Já₁	S₁	S_i	Ó_X
Já₂	S₁	S_j	Ó_y
…	…	…	…
Já_n	S₁	S_k	Ó_z
Já₁	S₂	S_{já ′}	Ó_X'
Já₂	S₂	S_{j '}	Ó_{y '}
…	…	…	…
Já_n	S₂	S_{k '}	Ó_{z ′}
…	…	…	…
Já₁	S_m	S_{já ″}	Ó_X"
Já₂	S_m	S_{j ″}	Ó_{y ″}
…	…	…	…
Já_n	S_m	S_{k ″}	Ó_{z ″}

Dvourozměrný

Stavy 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. Průsečíky řádek / sloupec označují další stavy a (volitelně) výstupy spojené s přechody stavu.

Tabulka přechodu stavu
(S: stav, I: vstup, O: výstup)
Vstup Aktuální stav	Já₁	Já₂	…	Já_n
S₁	S_i/Ó_X	S_j/Ó_y	…	S_k/Ó_z
S₂	S_{já ′}/Ó_X'	S_{j '}/Ó_{y '}	…	S_{k '}/Ó_{z ′}
…	…	…	…	…
S_m	S_{já ″}/Ó_X"	S_{j ″}/Ó_{z ″}	…	S_{k ″}/Ó_{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.

Tabulka přechodu stavu
(S: stav, I: vstup, O: výstup, -: nelegální)
Další stav Aktuální stav	S₁	S₂	…	S_m
S₁	Já_i/Ó_X	—	…	—
S₂	—	—	…	Já_j/Ó_y
…	…	…	…	…
S_m	—	Já_k/Ó_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.^[1] 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 jednom stroji s konečným stavem: „AND / OR tables“^[2] jsou podobné neúplným rozhodovací tabulky ve kterém rozhodnutí pro pravidla, která jsou přítomná, je implicitně aktivace souvisejícího přechodu.

Příklad

Příklad tabulky přechodu stavu spolu s odpovídajícími stavový diagram pro konečný stavový stroj je uveden níže:

Tabulka přechodu stavu
Vstup Aktuální stav	0	1
S₁	S₂	S₁
S₂	S₁	S₂

**Stavový diagram**

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₁ (první řádek) a obdrží vstup 1 (druhý sloupec), stroj zůstane ve stavu S.₁. Nyní, pokud je stroj ve stavu S₁ a přijme vstup 0 (první sloupec), stroj přejde do stavu S.₂.
Ve stavovém diagramu je první označen smyčkovou šipkou ze S₁ do S.₁ označeno 1 a ta je označena šipkou od S₁ do S.₂ označeno 0. Tento proces lze popsat statisticky pomocí Markovovy řetězy.

Pro nedeterministický konečný stavový stroj, vstup může způsobit, že stroj bude ve více než jednom stavu, tedy v jeho stavu nedeterminismus. 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:

Tabulka přechodu stavu
Vstup Aktuální stav	0	1
S₁	S₂	S₁
S₂	{S₁, S.₂}	S₂

**Stavový diagram**

Pokud je stroj ve stavu S₂ a přijme vstup 0, stroj bude ve dvou stavech současně, ve stavech S₁ a S.₂.

Transformace z / do stavového diagramu

Je možné nakreslit a 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 stát 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 států jako přijímající stát. To je také uvedeno ve formální definici stroje konečného stavu.

Viz také

Reference

^ Breen, Michael (2005), „Zkušenosti s použitím odlehčené metody formální specifikace pro produktovou řadu komerčních vestavěných systémů“ (PDF), Požadavky Engineering Journal, 10 (2): 161–172, CiteSeerX 10.1.1.60.5228, doi:10.1007 / s00766-004-0209-1
^ Leveson, Nancy; Heimdahl, Mats Per Erik; Hildreth, Holly; Reese, Jon Damon (1994), "Specifikace požadavků na systémy řízení procesů" (PDF), Transakce IEEE v softwarovém inženýrství, 20 (9): 684–707, CiteSeerX 10.1.1.72.8657, doi:10.1109/32.317428

Další čtení

Michael Sipser: Úvod do teorie výpočtu. PWS Publishing Co., Boston 1997 ISBN 0-534-94728-X

[Breen2005-1] Breen, Michael (2005), „Zkušenosti s použitím odlehčené metody formální specifikace pro produktovou řadu komerčních vestavěných systémů“ (PDF), Požadavky Engineering Journal, 10 (2): 161–172, CiteSeerX 10.1.1.60.5228, doi:10.1007 / s00766-004-0209-1

[LevesonEtAl1994-2] Leveson, Nancy; Heimdahl, Mats Per Erik; Hildreth, Holly; Reese, Jon Damon (1994), "Specifikace požadavků na systémy řízení procesů" (PDF), Transakce IEEE v softwarovém inženýrství, 20 (9): 684–707, CiteSeerX 10.1.1.72.8657, doi:10.1109/32.317428

[1]

[2]