Toggle menu
310,1 tis.
44
18
525,6 tis.
Hrvatska internetska enciklopedija
Toggle preferences menu
Toggle personal menu
Niste prijavljeni
Your IP address will be publicly visible if you make any edits.

Tablica prijelaza stanja

Izvor: Hrvatska internetska enciklopedija

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

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

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 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:

  1. Nacrtaj krugove koji predstavljaju zadana stanja.
  2. 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.
  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

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