 |
Ovaj članak ili dio članka nije pokriven izvorima. Pomozite Wikipediji navođenjem odgovarajućih knjiga, članaka u časopisima ili internetskih stranica. |
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).
| Događaji Stanje |
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.
| 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 tablice prijelaza stanja za stroj M zajedno sa odgovarajućim dijagramom stanja je dan dolje.
|
Dijagram stanja 
|
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) sa 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.
| Ulaz Stanje |
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 ISBN 0-534-94728-X