Dijagram stanja
From Wikipedia, the free encyclopedia
From Wikipedia, the free encyclopedia
Dijagrami stanja se koriste za grafički prikaz konačnih automata. Tabela prijelaza je jedan od drugih mogućih prikaza.
Ovaj članak ili neki od njegovih odlomaka nije dovoljno potkrijepljen izvorima (literatura, veb-sajtovi ili drugi izvori). |
Postoje razni oblici dijagrama stanja koji se razlikuju u pojedinim detaljima i imaju različitu semantiku.
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 "/":
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 "/".
"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).
S1 i S2 su stanja i S1 je prihvatljivo stanje. Svaki je brid labeliran sa ulazom.
S0, S1, i S2 su stanja. Svako je stanje labelirano sa "j / k" gdje je j ulaz i k izlaz.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.