Automata
/ɔːˈtɒm.ə.tə/ · Noun (plural) · Development · Origin: 1943
Definitions
Automata Theory is a branch of theoretical computer science that studies abstract mathematical models of computation called automata (singular: automaton). These models define different classes of machines with varying computational power and are used to understand the fundamental capabilities and limitations of computing. The simplest model, a finite automaton (FA), has a fixed number of states and processes input one symbol at a time, making it suitable for regular expressions and lexical analysis. Pushdown automata add a stack, enabling them to handle context-free grammars (programming language syntax). Turing machines, the most powerful model, have an infinite tape and can compute anything that is computable. Each automaton type corresponds to a class of formal languages (regular, context-free, recursive, recursively enumerable) in the Chomsky hierarchy. Automata theory is fundamental to compiler design (lexers use finite automata, parsers use pushdown automata), protocol verification, model checking, and understanding what problems computers can and cannot solve.
In plain English: Imaginary machines that read input one symbol at a time and follow rules to decide what to do next. They're the theory behind how compilers and regex engines work.
Example: "Your regex engine is literally a finite automaton under the hood — that's why it can't count matching parentheses."
Origin Story
The mathematical machines that determine what computers can and cannot do
**Automata theory** traces back to Alan Turing's 1936 paper describing an abstract machine (now called a **Turing machine**) that could compute anything computable. Warren McCulloch and Walter Pitts extended the idea in 1943 with finite automata models of neural activity.
The word **automaton** (plural: automata) comes from the Greek *automatos*, meaning "self-moving." Ancient Greeks used it for mechanical devices that appeared to move on their own. In computer science, automata are abstract machines with states, transitions, and acceptance conditions.
The **Chomsky hierarchy** (1956) organized automata into four levels: finite automata (regular languages), pushdown automata (context-free), linear-bounded automata (context-sensitive), and Turing machines (recursively enumerable). This hierarchy remains the foundation of compiler design, formal verification, and computability theory.
Coined by: Alan Turing, Warren McCulloch, Walter Pitts, Noam Chomsky
Context: 1936-1956, multiple institutions
Fun fact: Every regular expression you write is secretly a finite automaton. The regex engine converts your pattern to a state machine that processes input character by character. This is why some regex features (like backreferences) are computationally expensive -- they exceed what finite automata can handle.