U teoriji automata i sekvencijalnoj logici, tablica prijelaza (stanja) je tablica koja pokazuje u koje stanje (ili stanja u slučaju nedeterminističkog konačnog automata) konačni automat prelazi, ovisno o trenutnom stanju i drugim ulazima. Tablica stanja je u biti tablica istinitosti u kojoj su neki ulazi trenutno stanje, a izlazi uključuju sljedeće stanje, zajedno s ostalim izlazima.

Tablica stanja je jedan od mnogo načina specificiranja konačnog automata, pored dijagrama stanja i karakteristične jednadžbe.

Uobičajeni oblici Jednodimenzionalne tablice stanja

Također zvane i karakteristične tablice, jednodimenzionalne tablice stanja su sličnije tablicama istinitosti od dvodimenzionalnih inačica. Ulazi su obično smješteni s lijeve strane i odvojeni od izlaza, koji su na desnoj strani. Izlazi će predstavljati sljedeće stanje stroja. Slijedi jednostavan primjer konačnog automata s 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 tablice stanja Tablice prijelaza stanja su tipično dvodimenzionalne tablice. Postoje dva uobičajena načina za njihovo uređivanje.

Okomita (ili vodoravna) dimenzija označava trenutna stanja, vodoravna (ili okomita) dimenzija označava događaje, dok ćelije (presjeci redaka/stupaca) u tablici sadrže sljedeće stanje ako se događaj dogodi (i možebitnu akciju povezanu s ovim prijelazom).

+ Tablica 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)

Okomita (ili vodoravna) dimenzija označava trenutna stanja, vodoravna (ili okomita) dimenzija označava sljedeća stanja, dok presjeci redak/stupac sadrže događaj koji vodi ka nekom pojedinačnom sljedećem stanju.

+ Tablica 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 tablice prijelaza stanja za stroj M zajedno s odgovarajućim dijagramom stanja je dan dolje. + Tablica prijelaza stanja   UlazStanje 1 0 S1 S1 S2 S2 S2 S1   Dijagram stanja DFAexample.svg

Svi mogući ulazi stroja su pobrojani duž stupaca tablice. Sva moguća stanja su pobrojana duž redaka. Iz tablice prijelaza zadane gore, lako vidimo da ako je stroj u S1 (prvi redak), a sljedeći ulazni znak 1, stroj će ostati u stanju S1. Ako je ulazni znak 0, stroj će preći u stanje S2 kao što vidimo iz drugog stupca. Ovo je u dijagramu stanja označeno strelicom iz S1 u S2 označenom (labeliranom) s 0.

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

+ Tablica prijelaza stanja za NKA   UlazStanje 1 0 ε S1 S1 { S2, S3 } Φ S2 S2 S1 Φ S3 S2 S1 S1

Ovdje nedeterministički stroj u stanju S1 čitanjem znaka 0 na ulazu prelazi u dva stanja istovremeno, stanja S2 i S3. Posljednji stupac definira valjane prijelaze stanja specijalnog znaka ε. Ovaj istaknuti znak dopušta NKA prijelaz u različito stanje a da stroj ne pročita nijedan ulazni znak (ε-prijelaz). U stanju S3 stroj može preći u S1 a da ne pročita nijedan 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 prijeđi sve stupce u odgovarajućem retku 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.

Izvori Michael Sipser: Introduction to the Theory of Computation. PWS Publishing Co., Boston 1997

Kategorija:Teorija automata