Dijagram stanja

**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 
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.&nbsp;69, Hopcroft i Ullman (1979) p.&nbsp;16, Sipser (2006) p.&nbsp;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.&nbsp;34, Hopcroft i Ullman (1979) p.&nbsp;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 "**F**inalna" (zaustavljena, uhvaćena) stanja (Hopcroft i Ullman (1979) Slika 2.15, p.&nbsp;33).

### Primjeri 
#### DKA, NKA, GNKA, ili Mooreov automat 
*S1* i *S2* su stanja i *S1* je prihvatljivo stanje. Svaki je brid labeliran sa ulazom.
:DFAexample.svg

#### Mealyjev automat 
*S0*, *S1*, i *S2* su stanja. Svako je stanje labelirano sa "*j* / *k*" gdje je *j* ulaz i *k* izlaz.
:Mealymachine jaredwf.png

## Reference 
* Michael Sipser (2006), *Introduction to the Theory of Computation, Second Edition*, Thomson Course Technology, Boston. , .
* John Hopcroft i Jeffrey Ullman (1979) *Introduction to Automata Theory, Languarges, and Computation*, Addison-Wesley Publishing Company, Reading Mass, .
* Taylor Booth (1967) *Sequential Machines and Automata Theory*, John Wiley and Sons, New York. Library of Congress Catalog Card Number: 67-25924.

Kategorija:Teorija automata