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.

Tabela 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

• 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