# Dijagram stanja

### Izvor: Wikipedija

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

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

## [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), poopćeni nedeterministički konačni automat (PNKA) ili Mooreov automat, ulaz je naznačen na svakom bridu, obično blizu izvorišnog stanja. Za Mealyev automat, ulaz i izlaz su naznačeni na svakom bridu te obično odvojeni znakom "/":

  Ulazne i izlazne labele na bridu (strelici) Mealyevog 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 Mealyev 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 operira 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 (ovisno o simbolima napisanim 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, PNKA, ili Mooreov automat

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

#### [uredi] Mealyev automat

S0, S1, i S2 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.

- Taylor Booth (1967) Sequential Machines and Automata Theory, John Wiley and Sons, New York. Library of Congress Catalog Card Number: 67-25924.

Dobavljeno iz "http://hr.wikipedia.org../../../d/i/j/Dijagram_stanja.html"

Kategorija: Računski modeli

##### Views

- Članak
- Razgovor
- Trenutna inačica

##### Traži

##### Drugi jezici

- Deutsch
- English
- Español
- Suomi
- Français
- 日本語
- Português
- Русский
- Slovenčina