Automata theory

The automata theory is a branch of theoretical computer science that deals with the study of machines ( model computers ) and deals with the detachable from these machines problems.

It is an important tool of computability theory and complexity theory. Practical application it finds in the design of lexical scanners and parsers in compiler construction, as well as for the design of programming languages.

The automata theory is concerned with formal languages ​​and formal grammars, which, inter alia, typified by the Chomsky hierarchy, and with models for machines that can handle such languages ​​, in particular finite automata, pushdown automata, cellular automata and Turing machines.