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.

Tabulka přechodu
stavu (S: stav, I: vstup, O: výstup)
Vstup Aktuální stav Další stav Výstup
1 S 1 S i O x
I 2 S 1 S j O y
n S 1 S k O z
1 S 2 S i ' O x ′
I 2 S 2 S j ' O y '
n S 2 S k ' O z ′
1 S m S i ″ O x ″
I 2 S m S j " O y "
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.

Tabulka přechodu
stavu (S: stav, I: vstup, O: výstup)
Vstup
Aktuální stav
1 I 2 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.

Tabulka přechodu
stavu (S: stav, I: vstup, O: výstup, -: nelegální)
Další stav
Aktuální stav
S 1 S 2 S m
S 1 I I / O x - -
S 2 - - 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:

Tabulka přechodu stavu
Vstup
Aktuální stav
0 1
S 1 S 2 S 1
S 2 S 1 S 2
Stavový diagram
Stavový diagram FSM

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:

Tabulka přechodu stavu
Vstup
Aktuální stav
0 1
S 1 S 2 S 1
S 2 {S 1 , S 2 } S 2
Stavový diagram
Stavový diagram NFSM

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ů:

  1. Nakreslete kruhy, které představují dané stavy.
  2. 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.
  3. Určete stav jako počáteční stav . Počáteční stav je uveden ve formální definici stroje konečného stavu.
  4. 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