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

S1 i S2 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đajiStanje 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ćetrenutno 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   UlazStanje 1 0 S1 S1 S2 S2 S2 S1   Dijagram stanja  DFAexample.svg

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 S1 (prvi red), a sljedeći ulazni znak 1, mašina će ostati u stanju S1. Ako je ulazni znak 0, mašina će preći u stanje S2 kao što vidimo iz druge kolone. Ovo je u dijagramu stanja označeno strelicom iz S1 u S2 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   UlazStanje 1 0 ε S1 S1 { S2, S3 } Φ S2 S2 S1 Φ S3 S2 S1 S1

Ovdje nedeterministička mašina u stanju S1 čitanjem znaka 0 na ulazu prelazi u dva stanja istovremeno, stanja S2 i S3. 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 S3 mašina može preći u S1 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:
 Nacrtaj krugove koji predstavljaju zadana stanja.
 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.
 Označi stanje kao početno stanje. Početno stanje je zadano u formalnoj definiciji automata.
 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 

Kategorija:Teorija automata