Automata Theory & Formal Languages

Advanced Topics » Automata Theory & Formal Languages

Automata theory studies abstract machines and the classes of formal languages (sets of strings) they recognize. The standard models form a strict hierarchy by memory: finite automata (no memory beyond their state), pushdown automata (a stack), linear-bounded automata (a tape as long as the input), and Turing machines (unbounded tape). Each model corresponds exactly to a class of grammars in the Chomsky hierarchy. At the top, Turing machines capture everything that is computable at all, and some well-posed questions, such as whether a program halts, are provably beyond any of them.

The theory is also directly practical: regular expressions and lexers are finite automata, parsers for programming languages are pushdown automata, model checkers verify systems as automata over infinite words, and formal-language benchmarks are now used to measure what neural sequence models can learn.

flowchart TB
    subgraph RE["Recursively enumerable (Type 0): Turing machines"]
        subgraph DEC["Decidable: Turing machines that always halt"]
            subgraph CS["Context-sensitive (Type 1): linear-bounded automata"]
                subgraph CF["Context-free (Type 2): nondeterministic PDAs"]
                    subgraph DCF["Deterministic context-free: DPDAs, LR(1) grammars"]
                        subgraph REG["Regular (Type 3): finite automata"]
                            r1["(ab)*, even number of 1s"]
                        end
                        d1["a^n b^n, balanced parentheses"]
                    end
                    c1["w w^R (even palindromes)"]
                end
                s1["a^n b^n c^n, ww"]
            end
            e1["EXPSPACE-complete problems"]
        end
        h1["HALT"]
    end

Every inclusion is strict; each example belongs to its region but not to the next one inside it.

Languages, Alphabets, and Grammars

$\Sigma^{}$ is countably infinite, so the set of all languages, $2^{\Sigma^{}}$, is uncountable. Every machine has a finite description, so there are only countably many machines. A cardinality argument alone therefore shows that almost all languages are recognized by no machine; the rest of the subject determines which ones are.

A grammar is a 4-tuple $G = (V, \Sigma, R, S)$: a finite set $V$ of variables (non-terminals), a terminal alphabet $\Sigma$ disjoint from $V$, a start symbol $S \in V$, and a finite set $R$ of productions $\alpha \to \beta$. $L(G)$ is the set of terminal strings derivable from $S$. Restricting the shape of the productions gives the four levels of the Chomsky hierarchy (table below).

Finite Automata: DFA and NFA

A finite automaton reads its input once, left to right, and its only memory is which of finitely many states it is in.

Deterministic finite automata

Extend $\delta$ to strings by $\hat{\delta}(q, \varepsilon) = q$ and $\hat{\delta}(q, wa) = \delta(\hat{\delta}(q, w), a)$. Then

Example. Binary strings with an even number of 1s: state $E$ (even, start and accepting) and state $O$ (odd). Reading 0 stays put; reading 1 toggles.

stateDiagram-v2
    direction LR
    [*] --> E
    E --> E: 0
    O --> O: 0
    E --> O: 1
    O --> E: 1
    E --> [*]

A DFA decides membership in $O(n)$ time and $O(1)$ extra space, which is why lexers, protocol parsers, and network packet filters compile patterns to DFAs.

Nondeterministic finite automata

An NFA allows a set of possible next states and $\varepsilon$-moves: $\delta : Q \times (\Sigma \cup {\varepsilon}) \to 2^{Q}$. It accepts $w$ if some sequence of choices ends in an accepting state.

Example. Binary strings whose second-to-last symbol is 1. The NFA guesses when it has reached that position:

stateDiagram-v2
    direction LR
    [*] --> q0
    q0 --> q0: 0, 1
    q0 --> q1: 1
    q1 --> q2: 0, 1
    q2 --> [*]

Construction. For an NFA $N = (Q, \Sigma, \delta, q_0, F)$, let $E(S)$ be the $\varepsilon$-closure of a set of states. The DFA has states $2^{Q}$, start state $E({q_0})$, transitions $\delta’(S, a) = E\bigl(\bigcup_{q \in S} \delta(q, a)\bigr)$, and accepting states ${S : S \cap F \neq \varnothing}$. Only states reachable from the start need to be built. For the example above:

Each DFA state records the last two symbols read, which is exactly the information the language requires. Nondeterminism therefore adds no power to finite automata, only succinctness.

Regular Languages and Regular Expressions

Regular expressions over $\Sigma$ are built from $\varnothing$, $\varepsilon$, and each $a \in \Sigma$ using union $R \mid S$, concatenation $RS$, and Kleene star $R^{*}$:

The conversions that prove the theorem are all algorithms used in practice:

flowchart LR
    RX["Regular expression"] -- "Thompson's construction<br/>(size linear in the regex)" --> NFA["epsilon-NFA"]
    NFA -- "subset construction<br/>(up to 2^n states)" --> DFA["DFA"]
    DFA -- "Hopcroft minimization<br/>O(n log n)" --> MIN["Minimal DFA<br/>(unique)"]
    DFA -- "state elimination<br/>(can blow up exponentially)" --> RX
    RX -- "Brzozowski derivatives" --> DFA

• Thompson’s construction builds an $\varepsilon$-NFA from small gadgets for union, concatenation, and star, with $O(m)$ states for a regex of length $m$.
• State elimination (McNaughton–Yamada) removes NFA states one at a time, relabelling edges with regular expressions until one edge remains.
• Brzozowski derivatives: the derivative $a^{-1}L = {\, w : aw \in L \,}$ of a regular expression is again a regular expression, computable syntactically; repeatedly taking derivatives builds a DFA directly. Derivative-based matchers are used in modern regex engines, e.g. .NET’s non-backtracking mode.

Closure properties

Regular languages are closed under union, intersection, complement, concatenation, star, reversal, homomorphism, and inverse homomorphism. Complement swaps accepting and non-accepting states of a complete DFA. Intersection uses the product construction: run two DFAs in lockstep on pairs $(q, r)$ and accept when both accept. Closure is a proof tool: if $L \cap a^{}b^{} = {a^n b^n}$ and $a^{}b^{}$ is regular, then $L$ cannot be regular.

Myhill–Nerode and minimization

The theorem gives both an algorithm and a lower-bound technique. Hopcroft’s algorithm computes the minimal DFA in $O(n \log n)$ by refining a partition of states until no two states in a block are distinguishable. For lower bounds: the strings $a^0, a^1, a^2, \dots$ are pairwise inequivalent for $L = {a^n b^n}$ (the suffix $b^i$ separates $a^i$ from $a^j$), so $\equiv_L$ has infinitely many classes and $L$ is not regular. Unlike the pumping lemma, Myhill–Nerode is an exact characterization.

Regular expressions in practice

The “regex” syntax of most programming languages is not the regular expressions of theory:

• Backreferences such as (a+)b\1 describe non-regular languages (here ${a^n b a^n}$), and matching regexes with backreferences is NP-complete.
• Backtracking engines (PCRE, Java, JavaScript, Python’s re) try alternatives recursively and can take exponential time on patterns like (a|a)*b or (a+)+$ against a long string of as. Exploiting this is a ReDoS (regular-expression denial of service) attack.
• Automata-based engines (Thompson’s NFA simulation, lazy DFA construction) guarantee time linear in the input by giving up backreferences. Google’s RE2, Go’s regexp, and Rust’s regex crate work this way, and .NET added a non-backtracking option in .NET 7.

For untrusted input, an automata-based engine removes the ReDoS risk entirely.

The Pumping Lemma for Regular Languages

The pumping lemma is the standard tool for proving that a language is not regular. It follows from the pigeonhole principle: a DFA with $p$ states that reads $p$ or more symbols must revisit a state, and the loop between the two visits can be repeated or removed.

Example: ${ a^{n} b^{n} \mid n \geq 0 }$ is not regular. Suppose it is, with pumping length $p$, and take $w = a^{p} b^{p}$. Since $\lvert xy \rvert \leq p$, the piece $y$ is $a^{k}$ with $k \geq 1$. Then

contradicting (iii).

A useful way to structure these proofs is as a game: the adversary picks $p$, you pick $w \in L$, the adversary picks a legal split $xyz$, and you pick $i$ so that $xy^iz \notin L$. You must win against every split. The lemma is a necessary condition only: some non-regular languages satisfy it, so a failed pumping argument proves nothing. Myhill–Nerode is the complete test.

Context-Free Grammars and Pushdown Automata

Adding a stack to a finite automaton gives exactly the languages of nested structure: balanced brackets, arithmetic expressions, and the syntax of programming languages.

Context-free grammars

A context-free grammar (CFG) has productions $A \to \beta$ with a single variable on the left and $\beta \in (V \cup \Sigma)^{*}$. Balanced parentheses are generated by $S \to (S)\,S \mid \varepsilon$. The layered expression grammar

encodes precedence ($\times$ binds tighter than $+$) and left associativity through its layers, the template for expression parsers.

A grammar is ambiguous if some string has two distinct parse trees (equivalently, two leftmost derivations). The classic example is the “dangling else”: if a then if b then s else t has two parses unless the grammar forces else to attach to the nearest if. Some context-free languages, such as ${a^i b^j c^k : i = j \text{ or } j = k}$, are inherently ambiguous: every grammar for them is ambiguous. Whether a given CFG is ambiguous is undecidable.

Pushdown automata

The stack is unbounded but can only be accessed at the top. That suffices to count one thing: for $a^{n} b^{n}$, push a marker for each $a$, pop one for each $b$, and accept if the stack is back to $Z_0$ exactly when the input ends.

stateDiagram-v2
    direction LR
    [*] --> qPush
    qPush --> qPush: a, Z/AZ and a, A/AA
    qPush --> qPop: b, A/eps
    qPop --> qPop: b, A/eps
    qPush --> qAcc: eps, Z/Z
    qPop --> qAcc: eps, Z/Z
    qAcc --> [*]

PDA for ${a^n b^n : n \geq 0}$. An edge label “x, Y/W” means: read x, pop Y, push W (leftmost symbol on top).

Determinism matters here. Unlike finite automata, deterministic PDAs are strictly weaker than nondeterministic ones. The deterministic context-free languages (DCFLs) are exactly the languages of LR(1) grammars (Knuth, 1965) and can be parsed in linear time; they are the practically important class. Even-length palindromes ${ww^{R}}$ are context-free, since a nondeterministic PDA can guess the midpoint, but not deterministic. DCFLs are closed under complement, and equivalence of two DPDAs is decidable (Sénizergues, 1997; Gödel Prize 2002), whereas equivalence of general CFGs is undecidable.

Normal forms and parsing algorithms

Every CFG can be converted to Chomsky normal form, with rules $A \to BC$ or $A \to a$ (plus $S \to \varepsilon$ if needed). This makes parse trees binary and enables the CYK algorithm, a dynamic program in which table entry $(i, j)$ holds the variables that derive the substring from position $i$ to position $j$; it decides membership in $O(n^{3}\lvert G\rvert)$ time.

Parsing expression grammars (PEGs), popular in modern parser generators, look like CFGs but use ordered choice and are always unambiguous; they describe a different, incomparable family of languages.

The Pumping Lemma for Context-Free Languages

For CFLs, two substrings pump together, reflecting a parse subtree that repeats inside itself.

Take $p = b^{\lvert V\rvert + 1}$, where $b$ is the longest right-hand side. A parse tree for a string of length at least $p$ has height greater than $\lvert V\rvert$, so some root-to-leaf path repeats a variable $A$. The subtree under the upper $A$ derives $vAy$ around the lower one; repeating or deleting that segment pumps $v$ and $y$ simultaneously.

Example: ${ a^{n} b^{n} c^{n} \mid n \geq 0 }$ is not context-free. Take $w = a^{p} b^{p} c^{p}$. Since $\lvert vxy \rvert \leq p$, the window $vxy$ touches at most two of the three blocks. Pumping with $i = 2$ increases at most two of the three counts, so the result is not in $L$. A single stack can match one pair of counts, not three.

Closure properties of context-free languages

CFLs are closed under union, concatenation, star, homomorphism, and intersection with a regular language, but not under intersection or complement: ${a^n b^n c^m}$ and ${a^m b^n c^n}$ are both context-free, and their intersection is ${a^n b^n c^n}$. Since intersection can be written with union and complement (De Morgan), non-closure under complement follows.

The Chomsky Hierarchy

The inclusions are strict: $a^n b^n$ separates regular from context-free, $a^n b^n c^n$ separates context-free from context-sensitive, and the halting language separates decidable from recursively enumerable. The decidable languages sit strictly between context-sensitive and recursively enumerable; they are not one of Chomsky’s four grammar types because they are defined semantically (by a machine that halts on every input), not by the shape of productions.

Context-sensitive languages and LBAs

A linear-bounded automaton is a nondeterministic Turing machine that may only use the tape cells holding its input. Kuroda (1964) proved that LBAs recognize exactly the context-sensitive languages, so $\mathrm{CSL} = \mathrm{NSPACE}(n)$. Two classical questions about them:

• Complement. Kuroda asked whether CSLs are closed under complement. Immerman and Szelepcsényi independently proved in 1987 that $\mathrm{NSPACE}(s) = \mathrm{co}\text{-}\mathrm{NSPACE}(s)$ for $s(n) \geq \log n$, answering yes (Gödel Prize 1995).
• Determinism (the LBA problem). Whether deterministic LBAs recognize all CSLs, i.e. whether $\mathrm{DSPACE}(n) = \mathrm{NSPACE}(n)$, is still open.

Closure and decision properties

The drop-off in decidability between regular and context-free languages is why regular abstractions dominate program analysis and verification tooling.

Turing Machines

A configuration is the tape contents, head position, and state. On input $w$, $M$ may accept, reject, or run forever. The possibility of running forever is the source of every result in the rest of this page.

• $L$ is recursively enumerable (Turing-recognizable, semi-decidable) if some TM accepts exactly the strings of $L$; on other strings it may reject or loop.
• $L$ is decidable (recursive) if some TM halts on every input and accepts exactly $L$.

A universal Turing machine $U$ takes an encoding $\langle M, w\rangle$ and simulates $M$ on $w$. One fixed machine that runs any program is the theoretical basis of the stored-program computer, and the ability of machines to take machine descriptions as input is what makes the self-reference in the next section possible.

Busy beavers

The busy beaver function $\mathrm{BB}(n)$ is the maximum number of steps any halting $n$-state, 2-symbol Turing machine takes when started on a blank tape. $\mathrm{BB}$ grows faster than every computable function; if it were computable we could decide halting from blank tape by running a machine for $\mathrm{BB}(n)$ steps. Individual values can still be proved:

Determining $\mathrm{BB}(6)$ requires deciding the behaviour of machines whose halting is equivalent to open Collatz-like problems in number theory, which illustrates concretely why halting cannot be decided in general. Beyond some fixed size the values are not even provable: there is an explicit 745-state machine (2023) whose non-halting cannot be proved or refuted in ZFC set theory, so $\mathrm{BB}(745)$ is independent of ZFC.

Decidability and the Halting Problem

Proof. Suppose a TM $H$ decides $\mathrm{HALT}$. Build a machine $D$ that on input $\langle M \rangle$ runs $H$ on $\langle M, \langle M \rangle\rangle$ and does the opposite:

Run $D$ on $\langle D \rangle$. If $D$ halts, $H$ reported that it loops, so $D$ loops; if $D$ loops, $H$ reported that it halts, so $D$ halts. Both cases are contradictory, so $H$ cannot exist. $\blacksquare$

This is Cantor’s diagonal argument applied to machines: list all machines as rows and all machine descriptions as columns, and $D$ is built to differ from every row on the diagonal.

flowchart TB
    subgraph REC["Decidable = RE and co-RE"]
        E1["regular, context-free,<br/>context-sensitive languages"]
    end
    subgraph REonly["RE, not co-RE"]
        H["HALT, A_TM,<br/>'L(M) is nonempty'"]
    end
    subgraph COonly["co-RE, not RE"]
        C["complement of HALT,<br/>'L(M) is empty'"]
    end
    subgraph NEITHER["Neither RE nor co-RE"]
        N["'M halts on every input',<br/>'L(M1) = L(M2)'"]
    end

Semi-decidability. $\mathrm{HALT}$ is recursively enumerable: simulate $M$ on $w$ and accept if it halts. Its complement is not, because a language is decidable iff both it and its complement are recursively enumerable (run both recognizers in alternation; one of them must accept). So $\mathrm{HALT}$ witnesses that decidable $\subsetneq$ RE. Problems such as totality (“does $M$ halt on every input?”) are higher still in the arithmetical hierarchy, neither RE nor co-RE.

Reductions. If $A \leq_m B$ via a computable $f$ with $x \in A \Leftrightarrow f(x) \in B$, and $A$ is undecidable, then $B$ is undecidable. Reductions from $\mathrm{HALT}$ establish the undecidability of:

• the Post correspondence problem (given pairs of strings, is there a sequence whose top and bottom concatenations agree?), the usual intermediate step for grammar problems;
• CFG ambiguity, universality, and equivalence (via PCP);
• Hilbert’s tenth problem: solvability of polynomial Diophantine equations in integers (Matiyasevich, 1970, completing work of Davis, Putnam, and Robinson);
• the word problem for finitely presented groups (Novikov, 1955; Boone, 1958);
• Wang tiling of the plane (Berger, 1966).

Rice’s Theorem

Rice’s theorem generalizes the halting problem: every nontrivial property of what a program computes is undecidable.

Proof. Assume without loss of generality that $\varnothing$ lacks $P$ (otherwise use the complementary property). Let $L_P$ be an RE language with $P$, recognized by $M_P$. Given $\langle M, w\rangle$, build $N$ which on input $x$ first simulates $M$ on $w$ and, if that halts, runs $M_P$ on $x$. Then

A decider for $P$ applied to $\langle N\rangle$ would decide $\mathrm{HALT}$. $\blacksquare$

Consequences. Whether a program computes a constant function, ever outputs a particular value, is equivalent to another program, or recognizes an empty, finite, or regular language are all undecidable. The theorem concerns semantic properties of $L(M)$ only. Syntactic properties (“does $M$ have more than five states?”) and properties of bounded runs (“does $M$ halt within 1,000 steps?”) are decidable.

What verification does instead. Since exact answers are impossible in general, practical tools give up one of completeness, soundness, or full automation:

Model checkers for reactive systems use Büchi automata, finite automata that accept infinite words when some accepting state is visited infinitely often. Linear temporal logic formulas translate into Büchi automata, and checking a system against a formula reduces to emptiness of a product automaton, which is decidable.

Automata and Neural Sequence Models

Formal languages are now a standard probe of what neural networks can learn and represent. Delétang et al. (ICLR 2023, “Neural Networks and the Chomsky Hierarchy”) trained RNNs, LSTMs, and transformers on tasks at each level of the hierarchy and measured length generalization: LSTMs generalized on regular and some counter languages, transformers failed on many regular tasks such as parity, and networks augmented with external stack or tape memory climbed the hierarchy. Theoretical results match this picture: fixed-depth transformers without intermediate decoding steps fall in the circuit class $\mathsf{TC}^0$ and cannot track state for general finite automata, while chain-of-thought decoding restores that ability. See AI Mathematics for details.

References

1. Sipser, M. (2012). Introduction to the Theory of Computation, 3rd ed. Cengage.
2. Hopcroft, J., Motwani, R., & Ullman, J. (2006). Introduction to Automata Theory, Languages, and Computation, 3rd ed. Pearson.
3. Kozen, D. (1997). Automata and Computability. Springer.
4. Turing, A. (1936). “On Computable Numbers, with an Application to the Entscheidungsproblem.” Proc. London Mathematical Society.
5. Rabin, M. O., & Scott, D. (1959). “Finite Automata and Their Decision Problems.” IBM Journal of Research and Development.
6. Rice, H. G. (1953). “Classes of Recursively Enumerable Sets and Their Decision Problems.” Trans. AMS.
7. Knuth, D. E. (1965). “On the Translation of Languages from Left to Right.” Information and Control.
8. Cox, R. (2007). “Regular Expression Matching Can Be Simple And Fast.” swtch.com.
9. Delétang, G., et al. (2023). “Neural Networks and the Chomsky Hierarchy.” ICLR.
10. The bbchallenge Collaboration (2024). Proof that BB(5) = 47,176,870, verified in Coq. bbchallenge.org.

See Also

• Complexity Theory — resource-bounded computation: P, NP, PSPACE, and circuit classes
• Category & Type Theory — lambda calculus and the Curry–Howard view of computation
• AI Mathematics — learning theory and the expressivity of sequence models
• Approximation Algorithms — what can be computed efficiently when exact optimization is NP-hard
• Distributed Systems Theory — impossibility results and formal verification of protocols
• Cryptography — computational hardness as a resource
• Technology Hub — regular expressions, parsers, and language tooling in practice