Teorija automata

S Wikipedije, slobodne enciklopedije
Idi na navigaciju Idi na pretragu

Teorija automata je dio teoretske informatike, čiji je zadatak proučavanje automata i problema, kojim se takvi automati bave.

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 se bavi formalnim jezicima i formalnom grammatikom, koja se između ostalog tipizuje kroz Chomsky-hirarhiju, i sa modelima Automata, koji takve jezike mogu obrađivati, naročito konačni automati, podrumski-automati ili Turingove mašine.