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:

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 
 Konačni transduktor
 Vanjski linkovi 
 Free On-Line Dictionary of Computing opis konačnog automata
 NIST Dictionary of Algorithms and Data Structures opis konačnog automata
 Video lecture

Kategorija:Teorija automata