Dijagram stanja

S Wikipedije, slobodne enciklopedije
Jump to navigation Jump to search
Question book-new.svg Ovaj članak ili neka od njegovih sekcija nije dovoljno potkrijepljena izvorima (literatura, web-stranice ili drugi izvori).
Ako se pravilno ne potkrijepe validnim izvorima, sporne rečenice i navodi mogli bi biti obrisani. Pomozite Wikipediji tako što ćete navesti validne izvore putem referenci te nakon toga možete ukloniti ovaj šablon.

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.

Usmjereni graf[uredi | uredi izvor]

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

Primjeri[uredi | uredi izvor]

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

S1 i S2 su stanja i S1 je prihvatljivo stanje. Svaki je brid labeliran sa ulazom.

DFAexample.svg

Mealyjev automat[uredi | uredi izvor]

S0, S1, i S2 su stanja. Svako je stanje labelirano sa "j / k" gdje je j ulaz i k izlaz.

Mealymachine jaredwf.png

Reference[uredi | uredi izvor]

  • 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.
  • Taylor Booth (1967) Sequential Machines and Automata Theory, John Wiley and Sons, New York. Library of Congress Catalog Card Number: 67-25924.