Konačni automat

**Konačni automat** (još i **konačni stroj**, **automat konačnih stanja**) je diskretni matematički model koji se sastoji od konačnog broja stanja, prijelaza između tih stanja, i akcija koje obavlja.

## Koncepti i vokabular
Stanje sprema informacije o prošlosti,tj. odražava promjene na ulazu od početka sustava do sadašnjosti. Prijelaz indicira promjenu stanja i opisan je uvjetom koji treba biti zadovoljen da bi se prijelaz omogućio. Akcija je opis aktivnosti koja treba biti obavljena u danom trenutku. Postoji nekoliko tipova akcija, ovisno o tipu automata:
;Akcija ulaska: izvrši akciju *za vrijeme ulaska* u stanje
;Akcija izlaska: izvrši akciju *za vrijeme izlaska* iz stanja
;Ulazna akcija: izvrši akciju ovisno o trenutnom stanju i ulaznim uvjetima
;Prijelazna akcija: izvrši akciju dok se obavlja određeni prijelaz

Konačni automati su najčešće predstavljeni dijagramom stanja ili tablicom prijelaza. Najuobičajenija reprezentacija je prikazana dolje: kombinacija trenutnog stanja (B) i uvjeta (Y) uzrokuje prijelaz u sljedeće stanje (C). Potpune informacije o akcijama mogu biti dodane samo preko fusnota. Definicija konačnog automata koja uključuje potpune informacije o akcijama je moguća koristeći tablice prijelaza.

Pored uporabe u modeliranju reaktivnih sustava poput onih ovdje predstavljenih, uporaba konačnih automata je značajna u mnogim različitim područjima, uključujući elektrotehniku, lingvistiku, računarstvo, filozofiju, biologiju, matematiku i logiku. Konačni automati su klasa automata proučavana u teoriji automata i teoriji računanja

U računarstvu, konačni automati se koriste za modeliranje ponašanja aplikacije, dizajn digitalnih sustava, programsko inženjerstvo, jezične procesore, mrežne protokole te proučavanje računanja i jezika.

## Razredba
Postoje dvije različite skupine: prihvatitelji/priznavatelji i transduktori.

### Prihvatitelji i prepoznavatelji

**Prihvatitelji** i **prepoznavatelji** (također i **slijedni detektori**) stvaraju binarni izlaz, govoreći *da* ili *ne* kao odgovor na pitanje prihvaća li stroj ulaz ili ne. Za sva stanja konačnog automata kažemo da su ili prihvatljiva ili neprihvatljiva. U trenutku kad je sav ulaz obrađen, ukoliko je trenutno stanje prihvatljivo, ulaz je prihvaćen; inače je odbijen. U pravilu su ulazi simboli (karakteri); akcije se ne koriste. Primjer na slici 2 prikazuje konačni automat koji prihvaća engl. riječ *nice* - u ovom konačnom automatu jedino prihvatljivo stanje je pod brojem 7.

Stroj može biti opisan i definiranjem jezika koji bi sadržavao sve riječi koje stroj prihvaća i nijednu od onih koje odbija; kažemo da tad taj jezik stroj *prihvaća*. Po definiciji, jezici koje prihvaćaju konačni automati su regularni jezici - tj. jezik je regular ako postoji neki konačni automat koji ga prihvaća. (usp. Kleenejev teorem).

#### Početno stanje
Početno je stanje obično naznačeno strelicom koja "pokazuje ni od kuda" (Sipser (2006.) pp.&nbsp;34)

#### Prihvatljivo stanje
**Prihvatljivo stanje** (ponekad još zvano i **prihvaćajuće stanje**) je stanje u kojem je stroj uspješno obavio svoj namjenski postupak. Obično je predstavljen dvostruko koncentričnim krugom.

Primjer prihvatljivog stanja se pojavljuje na lijevoj strani ovog dijagrama determinističkog konačnog automata koji odlučuje sadrži li binarni ulaz paran broj znamenki 0.

:

*S*1 (koji je također i početno stanje) indicira stanje u kojem je pročitan paran broj znamenki 0 te je stoga definiran i kao prihvatljivo stanje.

### Transduktori
Transduktori generiraju izlaz na osnovu danog ulaza i/ili stanja koristeći akcije. Koriste se za upravljačke primjene. Ovdje razlikujemo dvije vrste:

;Mooreov automat: Konačni automat koristi samo akcije ulaska, tj. izlaz ovisi samo o stanju. Prednost Mooreovog modela jest pojednostavljenje ponašanja. Primjer na slici 3 prikazuje Mooreov konačni automat vrata lifta. Stroj stanja prepoznaje dvije naredbe: *command_open* i *command_close* koje okidaju promjene stanja. Akcija ulaska (E:) u stanju *Opening* pokreće motor koji otvara vrata, akcija ulaska u stanju *Closing* pokreće motor u drugom smjeru zatvarajući vrata. Stanja *Opened* i *Closed* ne obavljanju nikakve akcije, već samo služe za signalizaciju vanjskom svijetu (npr. ostalim strojevima stanja) situacije: "vrata su zatvorena" ili "vrata su otvorena".

;Mealyev automat: Konačni automat koristi samo ulazne akcije, tj. izlaz ovsi o ulazu i stanju. Uporaba Mealyjevog automata često vodi ka redukciji broja stanja. Primjer na slici 4 pokazuje Mealyjev konačni automat koji ostvaruje isto ponašanje kao i onaj u primjeru Mooreovog automata (ponašanje ovisi o izvršnom modelu ostvarenog konačnog automata i radit će za npr. virtualni KA ali ne i za događajem upravljani KA). Dvije su ulazne akcije (I:): "pokreni motor za zatvoriti vrata ako dođe naredba *command_close*" i "pokreni motor u drugom smjeru za otvoriti vrata ako dođe naredba *command_open*".

U praksi se koriste miješani modeli

Više se detalja o razlikama i uporabi Mooreovih i Mealyjevih modela, uključujući izvodivi primjer, može naći u vanjskoj tehničkoj bilješki "Mooreov ili Mealyjev model?" 

Daljnja je razlika između **determinističkih** (DKA) i **nedeterminističkih** (NKA, PNKA) automata. U determinističkim automatima, za svako stanje postoji točno jedan prijelaz za svaki mogući ulaz. U nedeterminističkim automatima može postojati više od jednog prijelaza za dani ulaz. Ova je razlika važna u praksi, ali ne i u teoriji, jer postoji algoritam koji može pretvoriti svaki NKA u istovjetni DKA, iako ova pretvorba obično znatno poveća složenost automata.

Konačni se automat sa samo jednim stanjem zove kombinatorni konačni automat i koristi samo ulazne akcije. Ovaj koncept je koristan u slučajevima kada se zahtijeva da više konačnih automata rade zajednički, te kad je zgodno razmatrati samo čisto kombinatorni dio kao oblik konačnog automata kako bi se prilagodilo alatima za dizajniranje.

## Logika konačnog automata

Sljedeće stanje i izlaz konačnog automata je funkcija ulaza i trenutnog stanja. Logika konačnog automata je prikazana na slici 5.

## Matematički model
Ovisno o tipu postoji nekoliko definicija. Konačni automat *prihvatitelj* je petorka (\Sigma, S, s_0, \delta, F), gdje:
* \Sigma je ulazna abeceda (konačan neprazan skup simbola).
* S je konačan neprazan skup stanja.
* s_0 je početno stanje, element skupa S. U nedeterminističkom konačnom automatu, s_0 je skup početnih stanja.
* \delta je funkcija prijelaza: \delta: S \times \Sigma \rightarrow S.
* F je skup konačnih stanja, (potencijalno prazan) podskup od S.

**Transduktorski** konačni automat je šestorka (\Sigma, \Gamma, S, s_0, \delta, \omega), gdje:
* \Sigma je ulazna abeceda (konačan neprazan skup simbola).
* \Gamma je izlazna abeceda (konačan neprazan skup simbola).
* S je konačan neprazan skup stanja.
* s_0 je početno stanje, element skupa S. U nedeterminističkom konačnom automatu, s_0 je skup početnih stanja.
* \delta je funkcija prijelaza: \delta: S \times \Sigma \rightarrow S.
* \omega je izlazna funkcija.

Ako je izlazna funkcija funkcija stanja i ulazne abecede(\omega: S \times \Sigma \rightarrow \Gamma), tad ta definicija odgovora **Mealyjevom modelu**. Ako izlazna funkcija ovisi samo o stanju (\omega: S \rightarrow \Gamma), tad ta definicija odgovora **Mooreovom moelu**. Konačni automat bez izlazne funkcije je poznat kao poluautomat ili prijelazni sustav.

## Optimizacija
Optimiziranje konačnog automata znači pronalaženje stroja sa minimalnim brojem stanja koji obavlja istu funkciju. Jedna je mogućnost korištenja implikacijske tablice ili Mooreova redukcijskog postupka. Druga je mogućnost odozdorni algoritam za acikličke konačne automate .

## Implementacija
### Sklopovske primjene

U digitalnim krugovima, konačni automat može biti načinjen koristeći programibilni logički uređaj, programibilni logički kontroler, logička vrata i bistabile ili releje. Konkretnije, sklopovsko ostvarenje zahtijeva registar za pohranjivanje varijabli stanja, blok kombinatorne logike koji određuje prijelaz stanja i drugi blok kombinatorne logike koji određuje izlaz konačnog automata. Jedan od klasičnih sklopovskih ostvarenja jest Richardov kontroler.

### Programske primjene
Sljedeći su koncepti često rabljeni za gradnju programske podrške konačnim automatima:
* Događajem upravljan konačni automat
* Virtualni konačni automat (VKA)
* Programiranje zasnovano na automatima

## Povezano
* Potisni automat
* Sekvencijalni sklop
* Turingov stroj

## Vanjske veze

* Opis iz ''Free On-Line Dictionary of Computing''
* unos u NIST rječniku algoritama i podatkovnih struktura
* Hijerarhijski strojevi stanja

## Reference

### Općenito
* Wagner, F., "Modeling Software with Finite State Machines: A Practical Approach", Auerbach Publications, 2006, .
* Cassandras, C., Lafortune, S., "Introduction to Discrete Event Systems". Kluwer, 1999, .
* Timothy Kam, *Synthesis of Finite State Machines: Functional Optimization*. Kluwer Academic Publishers, Boston 1997, 
* Tiziano Villa, *Synthesis of Finite State Machines: Logic Optimization*. Kluwer Academic Publishers, Boston 1997, 
* Carroll, J., Long, D. , *Theory of Finite Automata with an Introduction to Formal Languages*. Prentice Hall, Englewood Cliffs, 1989.
* Kohavi, Z., *Switching and Finite Automata Theory*. McGraw-Hill, 1978.
* Gill, A., *Introduction to the Theory of Finite-state Machines*. McGraw-Hill, 1962.
* Ginsburg, S., *An Introduction to Mathematical Machine Theory*. Addison-Wesley, 1962.

### Konačni automati (teorija automata) u teoretskom računarstvu
* 
* 
*  Opširna knjiga namijenjena specijalistima, napisana i za teoretske računalne znanstvenike i za električne inženjere. Uključuje detaljna objašnjenja tehnika minimizacije stanja, KA, Turingovih strojeva, Markovljevih procesa i neodlučivosti. Izvrstan tretman Markovljevih procesa.
*  Izvrsna knjiga. Izdaje se opetovano u različitim edicijama od 1974. (1974., 1980., 1989., 1999.).
*  Pristupa Church-Turingovoj tezi iz tri kuta: razine konačnih automata kao prihvatitelja formalnih jezika, teorije primitivne i paricijalne rekurzije, te moći običnih programskih jezika u svrhu ostvarenja algoritama, sve u jednom debelom svesku.
* 
*  Teška knjiga usredotočena na probleme strojnog tumačenja formalnih jezika, NP-potpunosti itd.
*  Različita i nešto manje zastrašujuća od prvog izdanja.
* 
* 
* 
* 
*  Minsky na stranicama 11-20 definira što je "stanje" u kontekstu konačnih automata. Njegov dijagram stanja je nekonvencijalan, Izvrsno, iako relativno čitljivo, ponekad čak i smiješno.
* 
*  Srž ovog teksta je apstraktna algebra, što je čini naprednijom i nešto manje pristušačnom od ostalih.
* 
*  cf. Konačni automati u poglavlju 29.
* 

### Apstraktni strojevi stanja u teoretskom računarstvu
* Yuri Gurevich (2000), *Sequential Abstract State Machines Capture Sequential Algorithms*, ACM Transactions on Computational Logic, vl. 1, no. 1 (July 2000), pages 77–111. http://research.microsoft.com/~gurevich/Opera/141.pdf

### Strojno učenje koristeći algoritme zasnovane na konačnim automatima
*  Širok prikaz iako temeljit i ponekad težak, namijenjen računalnim znanstvenicima i inženjerima. Poglavlje 13 *Reinforcement Learning* barata sa robotskim učenjem koje uključuje algoritme poput onih zasnovanih na strojevima stanja.

### Sklopovsko inženjerstvo: minimizacija stanja i sinteza sekvencijalnih sklopova
*  Opširna knjiga namijenjena specijalistima, napisana i za teoretske računalne znanstvenike i za električne inženjere. Uključuje detaljna objašnjenja tehnika minimizacije stanja, KA, Turingovih strojeva, Markovljevih procesa i neodlučivosti. Izvrstan tretman Markovljevih procesa.
*  Namijenjeno električnim inženjerima. Fokusiranije, manje zahtijevno od prethodne knjige. Njegov tretman računala je zastario. Zanimljiv pokušaj definiranja "algoritma".
*  Namijenjeno sklopovskim električnim inženjerima. Uključuje detaljna objašnjenja tehnika minimizacije stanja i tehnikama sinteze kombinatornih logičkih sklopova.
*  Namijenjeno sklopovskim električnim inženjerima. Izvrsna objašnjenja tehnika minimizacije stanja i tehnika sinteze kombinatornih i sekvencijalnih logičkih sklopova.

### Konačni Markovljevi ulančani procesi
::"Možemo zamisliti Markovljeve lance kao proces koji se sukcesivno pomiču kroz slijed stanja s1, s2, ..., sr. ... ako je u stanju si tada se pomiče na sljedeće stanje sj sa vjerojatnošću pij. Ove se vjerojatnosti mogu prikazati u obliku matrice prijelaza" (Kemeny (1959), pp. 384)
Konačni procesi Markovljevih lanaca su poznati i kao podposmaci konačnog tipa.
*  Opširna knjiga namijenjena specijalistima, napisana i za teoretske računalne znanstvenike i za električne inženjere. Uključuje detaljna objašnjenja tehnika minimizacije stanja, KA, Turingovih strojeva, Markovljevih procesa i neodlučivosti. Izvrstan tretman Markovljevih procesa.
*  Klasik . cf. poglavlje 6 "Finite Markov Chains"