Automata theory is a branch of theoretical computer science and formal sciences that studies abstract machines (automata) and the computational problems they can solve. It deals with the mathematical models of computation, such as finite automata, pushdown automata, and Turing machines, and their relationship with formal languages and grammars. Automata theory provides the foundations for compiler design, verification, artificial intelligence, and the classification of computational complexity.
1 Introduction
1.1 Historical background
The origins of automata theory can be traced to the 1930s and 1940s with the work of Alan Turing, Alonzo Church, and others on the limits of mechanical computation. Turing introduced the Turing machine in 1936 as a formal model of an algorithm. In the 1950s, finite automata were studied by researchers such as Warren McCulloch, Walter Pitts, and later by Claude Shannon. Noam Chomsky's work on formal grammars in the 1950s and 1960s provided a hierarchy that linked automata to language classes. The field matured through the 1960s and 1970s, becoming a cornerstone of theoretical computer science.
1.2 Basic concepts and definitions
1.2.1 Alphabet, string, and language
An alphabet is a finite non-empty set of symbols, usually denoted by Σ. A string (or word) over Σ is a finite sequence of symbols from Σ. The empty string, denoted by ε, has length zero. A language is a set of strings over a given alphabet. Languages can be finite or infinite and are the objects that automata accept or generate.
1.2.2 Determinism vs. nondeterminism
A deterministic automaton has exactly one possible transition for each input symbol from a given state. A nondeterministic automaton may have multiple transitions or none; it accepts an input if there exists at least one path that leads to an accepting state. Nondeterminism is a theoretical convenience; many nondeterministic models can be converted to equivalent deterministic ones, though sometimes with an exponential increase in states.
1.3 Role in formal sciences
Automata theory is a foundational component of formal sciences, particularly in the study of computation, languages, and complexity. It provides precise mathematical frameworks for analyzing the capabilities and limits of computing machines. The theory connects with mathematical logic, formal language theory, and grammar theory, and underpins fields such as compiler construction, verification, and computational biology.
2 Finite automata
2.1 Deterministic finite automaton (DFA)
2.1.1 Formal definition
A deterministic finite automaton (DFA) is defined as a 5-tuple (Q, Σ, δ, q₀, F), where:
- Q is a finite set of states.
- Σ is a finite alphabet.
- δ: Q × Σ → Q is the transition function.
- q₀ ∈ Q is the start state.
- F ⊆ Q is the set of accept (final) states.
For each input string, the DFA reads one symbol at a time, transitions deterministically, and accepts the string if it ends in an accept state.
2.1.2 State diagrams and transition tables
DFAs are commonly represented as state diagrams: nodes for states, directed edges labeled with input symbols for transitions, an arrow pointing to the start state, and double circles for accept states. Transition tables list states as rows and symbols as columns, with the next state in each cell.
2.2 Nondeterministic finite automaton (NFA)
2.2.1 Equivalence of DFA and NFA
Every NFA can be converted to an equivalent DFA that recognizes the same language. That is, nondeterminism does not change the class of languages accepted – both DFA and NFA accept exactly the regular languages. This equivalence is fundamental to the theory of finite automata.
2.2.2 Subset construction algorithm
The subset construction (also called powerset construction) transforms an NFA into a DFA. Each state of the DFA is a set of NFA states. From a DFA state S (a set of NFA states) and an input symbol a, the transition goes to the set of all NFA states reachable from any state in S by reading a. The start state is the ε-closure of the NFA's start state, and an accept state is any set containing at least one NFA accept state.
2.3 Finite automata with epsilon transitions
An NFA with ε-transitions (ε-NFA) allows transitions that consume no input symbol. This adds convenience in modeling certain constructs (e.g., optional parts). Formally, the transition function is δ: Q × (Σ ∪ {ε}) → 2^Q.
2.3.1 Removing epsilon transitions
Any ε-NFA can be converted to an ordinary NFA without ε-transitions by computing the ε-closure of each state and modifying the transition function accordingly. The resulting automaton accepts the same language.
2.4 Minimization of finite automata
Minimization reduces a DFA to the smallest possible number of states while preserving its language. The minimal DFA is unique up to renaming of states.
2.4.1 Myhill–Nerode theorem
The Myhill–Nerode theorem characterizes the regular languages in terms of an equivalence relation on strings: a language L is regular if and only if its Myhill–Nerode equivalence relation has finitely many equivalence classes. The number of classes equals the number of states in the minimal DFA for L.
2.4.2 Table-filling algorithm
The table-filling (or Moore) algorithm finds distinguishable states of a DFA. It marks pairs of states that are not equivalent (i.e., can be distinguished by some string). Initially, all pairs (p,q) where p ∈ F and q ∉ F are marked. Then, unmarked pairs are iteratively checked: if for some symbol a, the pair (δ(p,a), δ(q,a)) is already marked, then (p,q) is marked. The remaining unmarked pairs indicate equivalent states, which can be merged.
3 Pushdown automata
3.1 Formal definition and components
A pushdown automaton (PDA) extends a finite automaton with a stack (last-in, first-out memory). Formally, a PDA is a 7-tuple (Q, Σ, Γ, δ, q₀, Z₀, F), where:
- Q, Σ, q₀, F are as in finite automata.
- Γ is a finite stack alphabet.
- Z₀ ∈ Γ is the initial stack symbol.
- δ: Q × (Σ ∪ {ε}) × Γ → finite subsets of Q × Γ* is the transition function.
A transition may read an input symbol (or ε), pop the top stack symbol, and push a string of stack symbols.
3.2 Deterministic vs. nondeterministic pushdown automata
A deterministic PDA (DPDA) has at most one transition for each combination of state, input symbol (or ε), and top stack symbol. Nondeterministic PDAs (NPDA) can choose among multiple transitions. Deterministic PDAs accept a proper subset of context-free languages, called deterministic context-free languages, whereas nondeterministic PDAs accept all context-free languages.
3.3 Relationship with context-free grammars
Context-free grammars (CFGs) and PDAs are equivalent: every language generated by a CFG can be recognized by an NPDA, and every language accepted by an NPDA can be generated by a CFG.
3.3.1 Converting grammar to automaton
A CFG can be transformed into a PDA that simulates leftmost derivations. The PDA uses the stack to hold symbols, expanding nonterminals according to grammar productions and matching terminals with input.
3.3.2 Converting automaton to grammar
An NPDA can be converted to a CFG by constructing productions that represent the effect of pushing and popping. The grammar's nonterminals correspond to configurations of the PDA.
3.4 Closure properties of context-free languages
The class of context-free languages is closed under union, concatenation, and Kleene star, but not under intersection or complement. However, the intersection of a context-free language with a regular language is context-free. These properties are often used in parsing and language processing.
4 Turing machines
4.1 Standard Turing machine
4.1.1 Formal definition
A Turing machine (TM) is defined as a 7-tuple (Q, Σ, Γ, δ, q₀, B, F), where:
- Q is a finite set of states.
- Σ is the input alphabet (subset of Γ).
- Γ is the tape alphabet, including a blank symbol B.
- δ: Q × Γ → Q × Γ × {L, R} is the transition function (or partial function).
- q₀ ∈ Q is the start state.
- F ⊆ Q is the set of accept states.
The machine has an infinite tape divided into cells, a read/write head, and a finite state control.
4.1.2 Computation and halting
A computation begins with the input string on the tape (other cells blank) and the head at the leftmost symbol. The TM reads the current symbol, writes a symbol, moves left or right, and changes state. It halts (accepts) if it enters an accept state; it may also reject by entering a reject state or by falling into an infinite loop.
4.2 Variants of Turing machines
4.2.1 Multitape Turing machines
A multitape TM has several tapes, each with its own head. The transition can read and write all tapes simultaneously based on current states and symbols. Multitape TMs are equivalent in power to single-tape TMs, though they may be more efficient.
4.2.2 Nondeterministic Turing machines
A nondeterministic TM may have multiple possible transitions from a given configuration. It accepts an input if there exists a sequence of choices that leads to an accept state. Nondeterministic TMs are equivalent in power to deterministic ones, but the time overhead for simulation can be exponential.
4.3 Turing machine as a model of computation
4.3.1 Church–Turing thesis
The Church–Turing thesis states that any effectively computable function can be computed by a Turing machine. It is not a theorem but a widely accepted hypothesis about the nature of computation. All plausible general-purpose computational models have been shown equivalent to Turing machines.
4.3.2 Universal Turing machine
A universal Turing machine (UTM) can simulate any other Turing machine by reading a description of that machine from its tape. The UTM thus embodies the idea of a stored-program computer. Its existence demonstrates the computational universality of Turing machines.
5 Computability and decidability
5.1 Decidable and undecidable problems
A problem is decidable (or solvable) if there exists an algorithm (i.e., a Turing machine that halts on all inputs) that correctly answers yes/no for every instance. Undecidable problems have no such algorithm.
5.1.1 Halting problem
The halting problem asks whether a given Turing machine halts on a given input. Alan Turing proved that this problem is undecidable: no general algorithm exists to determine whether an arbitrary program halts. This result is fundamental in computability theory.
5.1.2 Post correspondence problem
The Post correspondence problem (PCP) is another classic undecidable problem. Given a set of dominoes (pairs of strings), the question is whether there exists a sequence of dominoes such that the concatenation of the top strings equals that of the bottom strings. PCP is undecidable and often used to prove undecidability of other problems.
5.2 Recursive and recursively enumerable languages
A language is recursive (or decidable) if there is a Turing machine that halts on every input, accepting strings in the language and rejecting those not. A language is recursively enumerable (RE) if there is a Turing machine that accepts exactly the strings in the language; it may loop forever on strings not in the language. The complement of an RE language is not necessarily RE.
5.3 Rice’s theorem
Rice’s theorem states that any nontrivial property of the language accepted by a Turing machine is undecidable. That is, there is no general algorithm to decide, given a TM, whether its language has a specific nontrivial property. This theorem highlights the prevalence of undecidability for semantic properties.
6 Formal languages and grammars
6.1 Chomsky hierarchy
Noam Chomsky classified formal grammars into four types, each corresponding to a class of automata and languages.
6.1.1 Type-3: Regular languages
Regular languages are described by regular expressions and accepted by finite automata. They are generated by right-linear grammars (productions of the form A → aB or A → a). Regular languages are closed under many operations and are the simplest in the hierarchy.
6.1.2 Type-2: Context-free languages
Context-free languages (CFLs) are generated by context-free grammars (productions of the form A → γ, where γ is a string of terminals and nonterminals) and accepted by pushdown automata. They are used for most programming language syntax.
6.1.3 Type-1: Context-sensitive languages
Context-sensitive languages (CSLs) are generated by context-sensitive grammars, where productions are of the form αAβ → αγβ (with γ non-empty). They are accepted by linear-bounded automata (Turing machines with tape limited to the input length). CSLs include many natural language constructs.
6.1.4 Type-0: Recursively enumerable languages
Type-0 languages are generated by unrestricted grammars (any production α → β with α non-empty). They are exactly the recursively enumerable languages accepted by Turing machines. This class includes all languages that can be effectively enumerated.
6.2 Regular expressions and finite automata
Regular expressions are algebraic descriptions of regular languages. Kleene's theorem states that regular expressions and finite automata are equivalent: every regular expression can be converted to an NFA, and every finite automaton can be described by a regular expression. This equivalence is fundamental for lexical analysis.
6.3 Context-free grammars and pushdown automata
Context-free grammars and pushdown automata are equivalent, as shown by the construction methods (Section 3.3). This relationship enables parsing algorithms such as the LL and LR parsers used in compilers.
7 Advanced topics
7.1 Abstract machines and complexity classes
7.1.1 Time and space complexity
Automata theory naturally leads to complexity classes based on resource bounds. For Turing machines, time complexity measures the number of steps, and space complexity measures the amount of tape used. For finite automata, no such resource limits are needed because they always halt after reading the input.
7.1.2 The class P and NP
P is the class of decision problems solvable by a deterministic Turing machine in polynomial time. NP is the class of problems solvable by a nondeterministic Turing machine in polynomial time, or equivalently, problems whose solutions can be verified in polynomial time. The P vs. NP question asks whether every problem that can be verified quickly can also be solved quickly. It remains an open problem in computer science.
7.2 Finite automata with output
7.2.1 Mealy and Moore machines
Mealy and Moore machines are finite automata that produce output on each transition (Mealy) or on each state (Moore). They model sequential circuits and controlled systems. The output in both cases depends on the present state; in Mealy machines it also depends on the input. They are equivalent in power: any Moore machine can be converted to a Mealy machine and vice versa.
7.3 Cellular automata
Cellular automata consist of a grid of cells, each in a finite state, that update synchronously according to local rules. They are not strictly finite automata in the classical sense but are related. They are studied in physics, biology, and computer science. The most famous example is Conway's Game of Life, which is Turing-complete.
7.4 Applications in software and hardware verification
7.4.1 Model checking
Model checking is an automated technique for verifying that a finite-state system (e.g., a hardware circuit or software protocol) satisfies a given temporal logic specification. It relies on algorithms that explore the state space of the system, often using automata-theoretic methods to represent behaviors and properties.
7.4.2 Lexical analysis and parsing
Finite automata are the basis for lexical analyzers (scanners) that tokenize source code. Regular expressions are compiled into DFAs for efficient matching. Pushdown automata underpin parsers for context-free grammars (e.g., LL, LR parsers). These applications make automata theory essential for compiler construction.