Konačni automat
 | Ovaj članak ili neki od njegovih odlomaka nije dovoljno potkrijepljen izvorima (literatura, veb-sajtovi ili drugi izvori). |
Konačni automat je model diskretnog matematičkog sistema koji se sastoji od konačnog broja stanja, prijelaza između tih stanja, i akcija koje obavlja. Stanje sprema informacije o prošlosti, tj. odražava promjene na ulazu od početka sistema do sadašnjosti. Prijelaz indicira promjenu stanja i opisan je uslovom koji treba biti zadovoljen da bi se prijelaz omogućio. Akcija je opis aktivnosti koja treba biti obavljena u datom trenutku. Postoji nekoliko tipova akcija, zavisno od tipa automata:
- Pristupna akcija
- izvrši akciju prilikom ulaska u stanje
- Izlazna akcija
- izvrši akciju za vrijeme izlaska iz stanja
- Ulazna akcija
- izvrši akciju zavisno od trenutnog stanja i ulaznih uslova
- Prijelazna akcija
- izvrši akciju dok se obavlja određeni prijelaz
Koncept konačnog automata je centralni koncept teorije računanja, s obzirom na to da počinje sa osnovnim procesima kojima završni bitovi pravilno enkodiranih informacija mogu teoretski biti rukovani inteligentno od strane mašine.
Konačni automati su najčešće predstavljeni dijagramom stanja ili tabelom prijelaza. Najuobičajenija prezentacija je prikazana dolje: kombinacija trenutnog stanja (B) i uslova (Y) uzrokuje prijelaz u sljedeće stanje (C). Potpune informacije o akcijama mogu biti dodate samo preko fusnota. Definicija konačnog automata koja uključuje potpune informacije o akcijama je moguća koristeći tabele prijelaza.
| Trenutno stanje/ Uslov |
Stanje A | Stanje B | Stanje C |
| Uslov X | ... | ... | ... |
| Uslov Y | ... | Stanje C | ... |
| Uslov Z | ... | ... | ... |
Pored upotrebe u modeliranju reaktivnih sistema poput onih ovdje predstavljenih, upotreba konačnih automata je značajna u mnogim različitim područjima, uključujući električno inžinjerstvo, 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 sistema, programsko inžinjerstvo, jezične procesore, mrežne protokole te proučavanje računjljivosti i jezika.
Također pogledajte
[uredi | uredi izvor]Vanjski linkovi
[uredi | uredi izvor]- Free On-Line Dictionary of Computing[mrtav link] opis konačnog automata
- NIST Dictionary of Algorithms and Data Structures opis konačnog automata
- Video lecture
| Teorija automata: formalni jezici i formalne gramatike | |||
|---|---|---|---|
| Chomskyjeva hijerarhija |
Gramatike | Jezici | Minimalni automat |
| Tip 0 | Neograničenih produkcija | Rekurzivno prebrojiv | Turingova mašina |
| n/a | (nema uobičajenog imena) | Rekurzivni | Odlučitelj |
| Tip 1 | Kontekstno ovisna | Kontekstno ovisni | Linearno ograničen |
| n/a | Indeksirana | Indeksirani | Ugniježđenog stoga |
| Tip 2 | Kontekstno neovisna | Kontekstno neovisni | Nedeterministički potisni |
| n/a | Deterministička kontekstno neovisna | Deterministički kontekstno neovisni | Deterministički potisni |
| Tip 3 | Regularna | Regularni | Konačni |
| Svaka kategorija jezika ili gramatika je pravi podskup nadređene kategorije. | |||
