What abstract machines can solve what classes of computational problems?
Automata theory is the study of abstract machines (mathematical models of computing devices) and the computational problems that can be solved using these machines.
Automata are abstract machines that process inputs and produce outputs based on defined rules. They are classified by their computational power:
- Finite automata - simplest, limited memory
- Pushdown automata - stack-based memory
- Turing machines - unlimited memory
The term comes from Greek “αυτόματα” meaning “something that does things by itself.”
- Studies abstract mathematical machines
- Closely related to formal language theory
- Automata are classified by the class of formal languages they recognize
- Used as theoretical models for computing machines
- Used for proofs about computability
- Built from: Formal Language, Finite Automaton, Pushdown Automaton
- Builds into: Chomsky Hierarchy, Formal Language Theory
- Related: Model of Computation, Theory of Computation
- More powerful automata can simulate less powerful ones
- The Chomsky hierarchy classifies languages by the automata that recognize them
Automata theory provides the framework for understanding computational power and classifying problems. It bridges abstract machines with formal languages and forms the foundation for computability theory.