Konačni automat
Izvor: Wikipedija
Konačni automat jest model diskretnog matematičkog sustava 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 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
- Izlazna akcija
- 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
Koncept konačnog automata je centralni koncept teorije izračunljivosti, s obzirom da počinje sa osnovnim procesima kojima mogu intelitentno od strane stroja rukovani konačni bitovi pravilno enkodiranih informacija.
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.
| Trenutno stanje/ Uvjet |
Stanje A | Stanje B | Stanje C |
| Uvjet X | ... | ... | ... |
| Uvjet Y | ... | Stanje C | ... |
| Uvjet Z | ... | ... | ... |
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 električno inženjerstvo, lingvistiku, računarstvo, filozofiju, biologiju, matematiku i logiku. Konačni automati su klasa automata proučavana u teoriji automata i teoriji izračunljivosti
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 izračunljivosti i jezika.
| Teorija automata: formalni jezici i formalne gramatike | |||
|---|---|---|---|
| Chomskyjeva hijerarhija |
Gramatike | Jezici | Minimalni automat |
| Tip 0 | Neograničenih produkcija | Rekurzivno prebrojiv | Turingov stroj |
| 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. | |||
