Tabela prijelaza

U teoriji automata i sekvencijalnoj logici, tabela prijelaza (stanja) je tabela koja pokazuje u koje stanje (ili stanja u slučaju nedeterminističkog konačnog automata) konačni automat prelazi, zavisno od trenutnog stanja i drugih ulaza. Tabela stanja je u biti tabela istinitosti u kojoj su neki ulazi trenutno stanje, a izlazi uključuju sljedeće stanje, zajedno s ostalim izlazima.

Tabela stanja je jedan od mnogo načina specificiranja konačnog automata, pored dijagrama stanja i karakteristične jednačine.

Uobičajeni oblici

Jednodimenzionalne tabele stanja

Također zvane i karakteristične tabele, jednodimenzionalne tabele stanja su sličnije tabelama istinitosti od dvodimenzionalnih varijanti. Ulazi su obično smješteni s lijeve strane i odvojeni od izlaza, koji su na desnoj strani. Izlazi će predstavljati sljedeće stanje mašine. Slijedi jednostavan primjer konačnog automata sa dva stanja i kombinatornim ulazima:

A	B	Trenutno stanje	Sljedeće stanje	Izlaz
0	0	S1	S2	1
0	0	S2	S1	0
0	1	S1	S2	0
0	1	S2	S2	1
1	0	S1	S1	1
1	0	S2	S1	1
1	1	S1	S1	1
1	1	S2	S2	0

S₁ i S₂ bi očito trebali predstavljati bitove 0 i 1, pošto jedan bit može imati samo dva stanja.

Dvodimenzionalne tabele stanja

Tabele prijelaza stanja su tipično dvodimenzionalne tabele. Postoje dva uobičajena načina za njihovo uređivanje.

• Vertikalna (ili horizontalna) dimenzija označava trenutna stanja, horizontalna (ili vertikalna) dimenzija označava događaje, dok ćelije (presjeci redova/kolona) u tabeli sadrže sljedeće stanje ako se događaj dogodi (i moguću akciju povezanu sa ovim prijelazom).

Tabela prijelaza stanja

Događaji Stanje	E1	E2	...	En
S1	-	Ay/Sj	...	-
S2	-	-	...	Ax/Si
...	...	...	...	...
Sm	Az/Sk	-	...	-

(S: stanje, E: događaj, A: akcija, -: nevaljali prijelaz)

• Vertikalna (ili horizontalna) dimenzija označava trenutna stanja, horizontalna (ili vertikalna) dimenzija označava sljedeća stanja, dok presjeci red/kolona sadrže događaj koji vodi ka nekom pojedinačnom sljedećem stanju.

Tabela prijelaza stanja

sljedeće trenutno	S1	S2	...	Sm
S1	Ay/Ej	-	...	-
S2	-	-	...	Ax/Ei
...	...	...	...	...
Sm	-	Az/Ek	...	-

(S: stanje, E: događaj, A: akcija, -: nemogući prijelaz)

Primjer

Primjer tabele prijelaza stanja za mašinu M zajedno sa odgovarajućim dijagramom stanja je dan dolje.

Tabela prijelaza stanja   Ulaz Stanje 1 0 S1 S1 S2 S2 S2 S1

Dijagram stanja

Svi mogući ulazi mašine su pobrojani duž kolona tabele. Sva moguća stanja su pobrojana duž redova. Iz tabele prijelaza zadane gore, lako vidimo da ako je mašina u S₁ (prvi red), a sljedeći ulazni znak 1, mašina će ostati u stanju S₁. Ako je ulazni znak 0, mašina će preći u stanje S₂ kao što vidimo iz druge kolone. Ovo je u dijagramu stanja označeno strelicom iz S₁ u S₂ označenom (labeliranom) sa 0.

Za nedeterministički konačni automat (NKA), novi ulazni znak može uzrokovati prijelaz mašine u skup stanja, a otud uostalom i nedeterminizam. Ovo je u tabeli prijelaza označeno parom vitičastih zagrada { } sa skupom svih odredišnih stanja među njima. Primjer je dan dolje.

Tabela prijelaza stanja za NKA

Ulaz Stanje	1	0	ε
S1	S1	{ S2, S3 }	Φ
S2	S2	S1	Φ
S3	S2	S1	S1

Ovdje nedeterministička mašina u stanju S₁ čitanjem znaka 0 na ulazu prelazi u dva stanja istovremeno, stanja S₂ i S₃. Posljednja kolona definira valjane prijelaze stanja specijalnog znaka ε. Ovaj istaknuti znak dozvoljava NKA prijelaz u različito stanje bez da mašina pročita ijedan ulazni znak (ε-prijelaz). U stanju S₃ mašina može preći u S₁ bez da pročita ijedan znak ulaznog niza. Ova dva slučaja čine opisani konačni automat nedeterminističkim.

Transformacije iz/u dijagram stanja

Moguće je nacrtati dijagram stanja iz tablice. Slijed jednostavnih koraka transformacije je sljedeći:

1. Nacrtaj krugove koji predstavljaju zadana stanja.
2. Za svako stanje pređi sve kolone u odgovarajućem redu i nacrtaj strelicu u odredišno stanje/stanja. Ako je automat NKA, moguće je da postoje višestruke strelice za ulazni znak.
3. Označi stanje kao početno stanje. Početno stanje je zadano u formalnoj definiciji automata.
4. Označi jedno ili više stanja kao prihvatljiva stanja. Ovo je također zadano u formalnoj definiciji.

Reference

• Michael Sipser: Introduction to the Theory of Computation. PWS Publishing Co., Boston 1997 ISBN 0-534-94728-X