Tablica prelaza stanja
Tabela prelaza stanja[uredi | uredi izvor]
U teoriji automata i sekvencijalnoj logici, tabela (tablica) prelaza stanja predstavlja tabularni prikaz promene stanja konačnih automata u zavisnosti od ulaza. Ona pokazuje u koje će se stanje (odnosno stanja u slučaju nedeterminističkih konačnih automata) pomeriti konačni automat u zavisnosti od trenutnog stanja i ulaznih podataka. Tabela stanja je zapravo tabela istinitosti u kojoj su neki ulazi trenutno stanje, a izlazi uključuju sledeće stanje, zajedno s ostalim izlazima. U ovoj tabeli ulazi se definišu kolonama a stanja vrstama.
Tabela stanja je jedan od mnogo načina opisivanja konačnog automata, pored dijagrama stanja i karakteristične jednačine. Ove tablice su korisne kada se skup svih ulaza može podeliti u relativno mali broj grupa i kada se skup svih mogućih ponašanja može podeliti u relativno mali broj stanja. U drugim slučajevima tabela može biti prevelika za rad.
Uobičajeni oblici[uredi | uredi izvor]
Jednodimenzionalne tablice stanja[uredi | uredi izvor]
Jednodimenzionalne tablice stanja se takođe zovu karakteristične tablice i one su sličnije tabelama istinitosti od dvodimenzionalnih. Ulazi se najčešće stavljaju sa leve strane i fizički se odvajaju od izlaza koji su na desnoj strani. Izlazi zapravo predstavljaju sledeće stanje u kojem će se mašina naći nakon čitanja ulaza. Sledi jednostavan primer konačnog automata sa dva stanja (S1 i S2 koji najverovatnije predstavljaju 0 ili 1 kako jedan bit može imati samo jednu od te dve vrednosti) i kombinatornim ulazima.
| A | B | Trenutno stanje | Sledeć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 |
Dvodimenzionalne tablice[uredi | uredi izvor]
Tabele stanje su, međutim, češće malo komplikovanije, i predstavljaju se dvodimenzionalno uz dva različita načina za njihovo uređivanje.
- U kolonama (odnosno vrstama) se nalaze trenutna stanja, u vrstama (odnosno kolonama) događaji, dok se u ćelijama tabele (u preseku vrsta i kolona) nalaze sledeća stanje u koje će automat preći ukoliko se ostvari događaj. (po mogućstvu može sadržati i akciju povezanu sa ovim prelazom)
| Događaji Stanje |
E1 | E2 | ... | En |
| S1 | - | Ay/Sj | ... | - |
| S2 | - | - | ... | Ax/Si |
| ... | ... | ... | ... | ... |
| Sm | Az/Sk | - | ... | - |
(S: stanje, E: događaj, A: akcija, -: nedozvoljeni prelaz)
- U kolonama (odnosno vrstama) se nalaze trenutna stanja, u vrstama (odnosno kolonama) sledeća stanja, dok se u ćelijama tabele nalaze događaji koji uzrokuju prelaz u naredno stanje (ponovo određeno presekom vrsta i kolona).
| sledeće trenutno |
S1 | S2 | ... | Sm |
| S1 | Ay/Ej | - | ... | - |
| S2 | - | - | ... | Ax/Ei |
| ... | ... | ... | ... | ... |
| Sm | - | Az/Ek | ... | - |
(S: stanje, E: događaj, A: akcija, -: nedozvoljeni prelaz)
Primer[uredi | uredi izvor]
U primeru koji sledi data je tabela prelaza stanja za automat M zajedno sa dijagramom stanja za isti automat.
|
Dijagram Stanja |
U kolonama ove tabele se nalaze svi mogući ulazi dok se moguća stanja u kojima se automat može naći nalaze u vrstama. Kombinujući stanje i ulaz, lako se vidi da će automat, ukoliko se nalazi u stanju S1 (prva vrsta) a na ulazu se nalazi 1 ostati u istom stanju S1. Ukoliko se na ulazu pojavi 0 automat prelazi u stanje S2 što se vidi u preseku prve vrste i druge kolone. Na dijagramu to se predstavlja strelicom koja spaja S1 i S2 označenom sa 0. Kod nedeterminističkih konačnih automata (NKA), automat iz jednog stanja čitanjem ulaza može da pređe u više različizih stanja (odatle i potiče naziv nedeterministički). Ovo se u tabelama stanja predstavlja vitičastim zagradama unutar kojih se nalaze sva stanja u koje se prelazi. Sledi primer.
| Ulaz Stanje |
1 | 0 | ε |
| S1 | S1 | { S2, S3 } | Φ |
| S2 | S2 | S1 | Φ |
| S3 | S2 | S1 | S1 |
Sada nedeterministički automat u stanju S1 čitajući ulaz 0 može da pređe u dva stanja S2 ili S3. Poslednja kolona definiše dozvoljene prelaze stanja čitanjem specijalnog znaka ε (prazne reči). Ovaj specijalni karakter dozvoljava NKA da pređe u drugo stanje bez čitanja ulaza. Kao što se vidi u trećoj vrsti, NKA se iz stanja S3 bez čitanja ulaza može prebaciti u stanje S1. Ova dva primera čine konačni automat nedeterminističkim.
Transformacije iz i u dijagram stanja[uredi | uredi izvor]
Lako je iz tabele stanja nacrtati dijagram stanja u samo nekoliko koraka.
- Nacrtati krugove koji predstavljaju zadana stanja
- Prolazeći kroz tablicu, za svako stanje nacrtati mogući prelaz, crtajući strelicu u moguća stanja i obečežavajući ih ulazom. Kod NKA iz jednog stanja može postojati više strelica
- Obeležiti početno satnje strelicom koja ne vodi ni iz jednog stanja.
- Obeležiti zavrsna stanja duplim krugom
Početna i završna stanja su zadana u formalnoj definiciji automata
Reference[uredi | uredi izvor]
- Michael Sipser: Introduction to the Theory of Computation. PWS Publishing Co., Boston 1997 ISBN 0-534-94728-X
- https://web.archive.org/web/20100331170515/http://sunset.usc.edu/classes/cs665_99/readings/week10/statetables.pdf