Teorija automata

Teorija automata je dio teoretske informatike, čiji je zadatak proučavanje automata i problema, kojim se takvi automati bave.
mini|300x300piksel|Automat opisan ovim dijagramom stanja počinje u stanju S 1 i mijenja stanja prateći strelice označene 0 ili 1 prema ulaznim simbolima kako stignu. Dvostruki krug označava S1 kao stanje prihvata. Pošto sve putanje od S1 do sebe sadrže paran broj strelica označenih 0, ovaj automat prihvata nizove koji sadrže parne brojeve 0.
Ova teorija je važna alatka u teorijama proračuna i kompleksiteta. Praktično se upotrebaljava kod izrade programskih prevodilaca (engl.: compiler) kao što su leksikalni skener (leksera) i parser. 

Teorija automata je usko povezana sa teorijom formalnog jezika. U ovom kontekstu, automati se koriste kao konačni prikazi formalnih jezika koji mogu biti beskonačni. Automati se često klasifikuju prema klasi formalnih jezika koje mogu prepoznati, kao u Chomsky hijerarhiji, koja opisuje odnos ugniježđenja između glavnih klasa automata. Automati igraju glavnu ulogu u teoriji računanja, konstrukciji kompajlera, umjetnoj inteligenciji, raščlanjivanju i formalnoj verifikaciji.

Teorija apstraktnih automata razvijena je sredinom 20. stoljeća u vezi s konačnim automatima. Teorija automata se u početku smatrala granom teorije matematičkih sistema, proučavajući ponašanje sistema diskretnih parametara. Rani rad u teoriji automata razlikovao se od prethodnog rada na sistemima korišćenjem apstraktne algebre za opisivanje informacionih sistema, a ne diferencijalnog računa za opisivanje materijalnih sistema. Teoriju pretvarača konačnog stanja razvile su različite istraživačke zajednice pod različitim nazivima.: "The theories, now well developed, of the "finite-state machine" (Gill, 1962), of the "noiseless transducer" (Shannon and Weaver, 1949), of the "state-determined system" (Ashby, 1952), and of the "sequential circuit", are essentially homologous." Raniji koncept Turingove mašine je takođe bio uključen u disciplinu zajedno sa novim oblicima automata sa beskonačnim stanjem, kao što su automati za spuštanje.

 Reference 

 Vanjski linkovi 

 https://www.brics.dk/automaton/

Kategorija:Računarstvo