Konačni automat

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:

Turnstile
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 ... ... ...
Tabela prijelaza

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

Vanjski linkovi uredi

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.