Automata theory is the branch of computer science that studies abstract machines, idealized computing devices defined by simple rules, and asks what each kind of machine can and cannot do. The machines form a hierarchy of increasing power: finite automata at the bottom, pushdown automata in the middle, and Turing machines at the top, each able to recognize a strictly larger class of languages than the one below it.
The Stanford Encyclopedia of Philosophy’s entry on computability and complexity describes how several researchers in the 1930s independently defined models of computation, including Turing machines, Church’s lambda calculus, and Kleene’s formal systems, and how these turned out to be equivalent in power. That equivalence is the heart of automata theory: different-looking machines can compute exactly the same things, which lets us speak of computational power as a property of the problem rather than of the device.
A foundational technical result in the field is Michael Rabin and Dana Scott’s 1959 paper “Finite Automata and Their Decision Problems,” which formalized nondeterministic automata and showed how to convert them into equivalent deterministic ones. Their analysis of what questions about automata can be decided algorithmically set the template for the decision-problem style of reasoning that runs through the whole subject.
Automata theory is not an abstraction without payoff. It explains why regular expressions match the patterns they do, why a context-free grammar is the right tool for the nested structure of programming languages, and where the boundary of mechanical computation lies. Every compiler’s lexer and parser is, at bottom, an automaton chosen to fit the language it must read.