WikiSysop: zamjena teksta

2022-03-16T10:48:37Z

zamjena teksta

←Starija inačica		Inačica od 16. ožujak 2022. u 10:48
Redak 1:		Redak 1:
	~~<!--'''Dijagram stanja'''-->'''~~Dijagram stanja''' (još i '''dijagram prijelaznih stanja''', '''grafikon prijelaznih stanja''' i '''shematski prikaz prijelaznih stanja''' <ref name="InfoRjecnik">Kiš Miroslav, ''Englesko-hrvatski i hrvatsko-engleski informatički rječnik'', Zagreb, Naklada Ljevak, 2000., str. 862</ref>) se koristi za grafički prikaz [[konačni automat\|konačnih automata]]. [[Tablica prijelaza]] je jedan od drugih mogućih prikaza.		Dijagram stanja''' (još i '''dijagram prijelaznih stanja''', '''grafikon prijelaznih stanja''' i '''shematski prikaz prijelaznih stanja''' <ref name="InfoRjecnik">Kiš Miroslav, ''Englesko-hrvatski i hrvatsko-engleski informatički rječnik'', Zagreb, Naklada Ljevak, 2000., str. 862</ref>) se koristi za grafički prikaz [[konačni automat\|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.		Postoje razni oblici dijagrama stanja koji se razlikuju u pojedinim detaljima i imaju različitu semantiku.

WikiSysop: Bot: Automatski unos stranica

2021-08-20T01:46:14Z

Bot: Automatski unos stranica

Nova stranica

'''Dijagram stanja''' (još i '''dijagram prijelaznih stanja''', '''grafikon prijelaznih stanja''' i '''shematski prikaz prijelaznih stanja''' <ref name="InfoRjecnik">Kiš Miroslav, ''Englesko-hrvatski i hrvatsko-engleski informatički rječnik'', Zagreb, Naklada Ljevak, 2000., str. 862</ref>) se koristi za grafički prikaz [[konačni automat|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.

== 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 "'''F'''inalna" (zaustavljena, uhvaćena) stanja (Hopcroft i Ullman (1979) Slika 2.15, p. 33).

=== Primjeri ===
==== DKA, NKA, PNKA, ili Mooreov automat ====

''S1'' i ''S2'' su stanja i ''S1'' je prihvatljivo stanje. Svaki je brid labeliran sa ulazom.
:[[Datoteka:DFAexample.svg|DFAexample.svg]]

==== Mealyev automat ====

''S0'', ''S1'', i ''S2'' su stanja. Svako je stanje labelirano sa "''j'' / ''k''" gdje je ''j'' ulaz i ''k'' izlaz.
:[[Datoteka:Mealymachine jaredwf.png|Mealymachine jaredwf.png]]

== Izvori ==

{{izvori}}

* [[Michael Sipser]] (2006), ''Introduction to the Theory of Computation, Second Edition'', Thomson Course Technology, Boston. {{ISBN|978-0-534-95097-2}}, {{ISBN|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.

[[Kategorija:Računski modeli]]

Dijagram stanja - Povijest promjena

WikiSysop: zamjena teksta

WikiSysop: Bot: Automatski unos stranica