Tablica prijelaza stanja

Izvor: Wikipedija
Skoči na: orijentacija, traži

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[uredi VE | uredi]

Jednodimenzionalne tablice stanja[uredi VE | uredi]

Također zvane i karakteristične tablice, jednodimenzionalne tablice stanja su sličnije tablicama 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 stroja. 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 tablice stanja[uredi VE | uredi]

Tablice prijelaza stanja su tipično dvodimenzionalne tablice. 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 redaka/stupaca) u tablici sadrže sljedeće stanje ukoliko se događaj dogodi (i možebitnu akciju povezanu sa ovim prijelazom).
Tablica prijelaza stanja
  Događaji
Stanje
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 redak/stupac sadrže događaj koji vodi ka nekom pojedinačnom sljedećem stanju.
Tablica prijelaza stanja
      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[uredi VE | uredi]

Primjer tablice prijelaza stanja za stroj M zajedno sa odgovarajućim dijagramom stanja je dan dolje.

Tablica prijelaza stanja
  Ulaz
Stanje
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 ukoliko je stroj u S1 (prvi redak), a sljedeći ulazni znak 1, stroj će ostati u stanju S1. Ukoliko 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 uzrokovati 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
  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 dozvoljava NKA prijelaz u različito stanje bez da stroj pročita ijedan ulazni znak (ε-prijelaz). U stanju S3 stroj 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[uredi VE | uredi]

Moguće je nacrtati dijagram stanja iz tablice. Slijed jednostavnih koraka transformacije je sljedeći:

  1. Nacrtaj krugove koji predstavljaju zadana stanja.
  2. Za svako stanje pređi sve stupce u odgovarajućem retku i nacrtaj strelicu u odredišno stanje/stanja. Ukoliko je automat NKA, moguće je da postoje višestruke strelice za ulazni znak.
  3. Označi stanje kao početno stanje. Početno stanje je zadano u formalnoj definiciji automata.
  4. Označi jedno ili više stanja kao prihvatljiva stanja. Ovo je također zadano u formalnoj definiciji.

Izvori[uredi VE | uredi]

  • Michael Sipser: Introduction to the Theory of Computation. PWS Publishing Co., Boston 1997 ISBN 0-534-94728-X