Dijagram stanja

Sa Wikipedije, slobodne enciklopedije

Dijagrami stanja se koriste za grafički prikaz konačnih automata. Tabela prijelaza je jedan od drugih mogućih prikaza.

Postoje razni oblici dijagrama stanja koji se razlikuju u pojedinim detaljima i imaju različitu semantiku.

Sadržaj

1 Usmjereni graf
- 1.1 Primjeri
  - 1.1.1 DKA, NKA, GNKA, ili Mooreov automat
  - 1.1.2 Mealyjev automat
2 Reference

[uredi] Usmjereni graf

Klasični oblik dijagrama stanja za konačni automat je usmjereni graf (digraf) sa sljedećim elementima:

Stanja Q: konačan skup vrhova obično predstavljenih krugovima i označenih (labeliranih) sa jedinstvenim simbolom oznake ili riječima napisanim unutar njih. (Booth (1967) p. 69, Hopcroft i Ullman (1979) p. 16, Sipser (2006) p. 34).

Ulazni simboli Σ: konačna kolekcija ulaznih "simbola" (znakova) ili oznaka Σ (Booth, Hopcroft i Ullman, Sipser). Za deterministički konačni automat (DKA), nedeterministički konačni automat (NKA), generalizirani nedeterministički konačni automat (GNKA) ili Mooreov automat, ulaz je naznačen na svakom bridu, obično blizu izvorišnog stanja. Za Mealyjev automat, ulaz i izlaz su naznačeni na svakom bridu te obično odvojeni znakom "/":

Ulazne i izlazne labele na bridu (strelici) Mealyjevog automata: "1/0" označava da je simbol "1" uzrokovao simbol "0" kao izlaz.

Izlazni simboli Z: konačan skup izlaznih "simbola" ili oznaka (Booth, Hopcroft i Ullman, Sipser). Za Mealyjev automat, ulaz i izlaz su naznačeni na svakom bridu kao što je gore prikazano. Za Mooreov automat, izlaz stanja se obično piše unutar kruga koje predstavlja stanje, odvojeno od oznake stanja znakom "/".

Primjer: Ako stanje ima više izlaza (npr. "a= motor operiše obrnuto od smjera kazaljke na satu=1, b= oprez svjetlo isključeno=0"), dijagram bi to trebao odražavati : npr. "q5/1,0" označava stanje q5 sa izlazima a=1, b=0. Ova će oznaka biti zapisana unutar kruga koje predstavlja stanje.

"Izlazna funkcija ω" predstavlja preslikavanje ω ulaznih simbola I x stanja Q u izlazne simbole Z (Booth).

Bridovi δ: predstavljaju "prijelaze" između stanja koje ulazi uzrokuju (zavisno od simbola napisanih na bridovima). Brid je obično predstavljen strelicom usmjerenom od trenutnog stanja prema sljedećem. δ predstavlja preslikavanje ulaznih simbola I x stanja Q u izlazne simbole Z (Booth, Hopcroft i Ullman, Sipser).

Početno stanje qo: (nije prikazano u donjim primjerima). Početno stanje qo je obično predstavljeno "strelicom bez izvorišnog stanja koja pokazuje na njega". (Sipser (2006) p. 34, Hopcroft i Ullman (1979) p. 16). U starijim udžbenicima (npr. Booth (1969), McCluskey (1965), Hill i Peterson (1974)) početno stanje nije istaknuto i mora biti inferirano iz teksta problema.

Prihvatljiva stanja F: Ako korištena - predstavljaju kolekciju dvostrukih koncentričnih krugova i koriste se za predstavljanje prihvatljivih stanja automata (Hopcroft i Ullman, Sipser). Ponekad prihvatljiva stanja funkcioniraju kao "Finalna" (zaustavljena, uhvaćena) stanja (Hopcroft i Ullman (1979) Slika 2.15, p. 33).

[uredi] Primjeri

[uredi] DKA, NKA, GNKA, ili Mooreov automat

S₁ i S₂ su stanja i S₁ je prihvatljivo stanje. Svaki je brid labeliran sa ulazom.

[uredi] Mealyjev automat

S₀, S₁, i S₂ su stanja. Svako je stanje labelirano sa "j / k" gdje je j ulaz i k izlaz.

[uredi] Reference

Michael Sipser (2006), Introduction to the Theory of Computation, Second Edition, Thomson Course Technology, Boston. ISBN-13: 978-0-534-95097-2, ISBN-10: 0-534-95097-3.

John Hopcroft i Jeffrey Ullman (1979) Introduction to Automata Theory, Languarges, and Computation, Addison-Wesley Publishing Company, Reading Mass, ISBN 0-201-02988-X.