Automata theory

Summary

Automata theory is the part of the theory of computation that studies abstract machines, called automata, and the problems they can solve. Its basic objects are finite-state machines, pushdown automata and Turing machines. Each kind of machine recognizes a class of formal languages, and these classes form the Chomsky hierarchy. The theory underlies compilers, text search, hardware design and the verification of programs.