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:

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).

(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.

(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.

| &nbsp;
| align="center" | **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.

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