Tilstandsovergangstabell

I automatteori og sekvensiell logikk er en tilstandsovergangstabell en tabell som viser hvilken tilstand en gitt begrenset automat vil flytte til , basert på gjeldende tilstand og andre innganger. En tilstandstabell er i hovedsak en sannhetstabell der noen av inngangene er den nåværende tilstanden, og utgangene inkluderer den neste tilstanden, sammen med andre utganger.

En tilstandstabell er en av mange måter å spesifisere en tilstandsmaskin på , andre måter er et tilstandsdiagram og en karakteristisk ligning .

Når du har å gjøre med en ikke-deterministisk endelig automat , viser overgangstabellen alle tilstandene automaten vil flytte til.

Vanlige skjemaer

Endimensjonale tilstandstabeller

Også kalt funksjonstabeller , endimensjonale tilstandstabeller er mer som sannhetstabeller enn de todimensjonale versjonene. Inngangene er normalt plassert til venstre, og atskilt fra utgangene, som er til høyre. Utgangene vil representere den neste tilstanden til maskinen. Her er et enkelt eksempel på en tilstandsmaskin med to tilstander og to kombinasjonsinnganger:

EN	B.	Faktisk tilstand	Neste status	Avgang
0	0	S 1	S2 _	1
0	0	S2 _	S 1	0
0	1	S 1	S2 _	0
0	1	S2 _	S2 _	1
1	0	S 1	S 1	1
1	0	S2 _	S 1	1
1	1	S 1	S 1	1
1	1	S2 _	S2 _	0

S1 og S2 vil sannsynligvis representere de individuelle bitene 0 og 1, siden en enkelt bit bare har to tilstander .

Todimensjonale tilstandstabeller

Tilstandsovergangstabeller er normalt todimensjonale tabeller. Det er to vanlige måter å bygge dem på.

• Den vertikale dimensjonen indikerer gjeldende tilstander, den horisontale dimensjonen indikerer hendelser, og cellene (rad/kolonne skjæringspunkter) i tabellen inneholder den neste tilstanden hvis en hendelse inntreffer (og muligens handlingen knyttet til denne tilstandsovergangen).

Overgangstabell for staten

Begivenheter State	jeg 1	E 2	...	I n
S 1	-	A y /S j	...	-
S2 _	-	-	...	A x /S i
...	...	...	...	...
y m	A z /S k	-	...	-

(S: status, E: hendelse, A: handling, -: ulovlig overgang)

• Den vertikale dimensjonen indikerer gjeldende tilstander, den horisontale dimensjonen indikerer de neste tilstandene, og kryssene mellom rad og kolonne inneholder hendelsen som vil føre til den neste bestemte tilstanden.

Overgangstabell for staten

neste aktuelle	S 1	S2 _	...	y m
S 1	A y /E j	-	...	-
S2 _	-	-	...	A x /E i
...	...	...	...	...
y m	-	A z /E k	...	-

(S: status, E: hendelse, A: handling, -: overgang umulig)

Eksempel

Et eksempel på en tilstandsovergangstabell for en maskin M sammen med det tilsvarende tilstandsdiagrammet er gitt nedenfor.

Overgangstabell for staten   Statusinngang _ 1 0 S 1 S 1 S2 _ S2 _ S2 _ S 1

Tilstandsdiagram

Alle mulige innganger til maskinen er listet opp gjennom kolonnene i tabellen. Alle mulige tilstander er oppført på tvers av radene. Fra tilstandsovergangstabellen ovenfor er det lett å se at hvis maskinen er i S 1 (den første raden), og neste inndata er tegn 1 , vil maskinen forbli i S 1 . Hvis det kommer et 0 - tegn , vil maskinen gå over til S 2 som kan sees fra den andre kolonnen. I diagrammet er dette angitt med pilen fra S 1 til S 2 merket 0 .

For en ikke-deterministisk endelig automat (NDFA) kan en ny inngang føre til at maskinen er i mer enn én tilstand, siden den er ikke-deterministisk. Dette er angitt i en tilstandsovergangstabell med et parentes-par { } med et sett med alle måltilstander mellom seg. Et eksempel er gitt nedenfor.

Statlig overgangstabell for en AFND

Statusinngang _	1	0	ε
S 1	S 1	{ S2 , S3 }	Φ
S2 _	S2 _	S 1	Φ
S3 _	S2 _	S 1	S 1

Her vil en ikke-deterministisk maskin i tilstand S1 som leser en inngang på 0 føre til at den er i to tilstander samtidig , tilstander S2 og S3 . Den siste kolonnen definerer de juridiske overgangstilstandene for spesialtegnet, ε. Dette spesialtegnet lar AFND-er flytte til en annen tilstand når det ikke er noen inndata. I tilstand S 3 kan AFND flytte til S 1 uten å bruke noen inndatategn. De to foregående tilfellene konfigurerer den ikke-deterministiske endelige automaten.

Transformasjoner fra/til tilstandsdiagram

Det er mulig å tegne et tilstandsdiagram med utgangspunkt i tabellen. En mulig sekvens av trinn å følge er som følger:

1. Tegn sirkler for å representere de gitte tilstandene.
2. For hver av tilstandene, se på den tilsvarende raden og tegn en pil for hver av måltilstandene. Det kan være flere piler for samme inndatategn hvis automaten er en AFND.
3. Angir en tilstand som starttilstand . Starttilstanden er gitt i den formelle definisjonen av automaten.
4. Utpeker en eller flere stater som den endelige tilstanden (eller også kalt aksept). Dette er også gitt i den formelle definisjonen.

Referanser

• Michael Sipser: Introduksjon til teorien om beregning . PWS Publishing Co., Boston 1997 ISBN 0-534-94728-X