13. Formal Languages and Automata

A compiler has to decide whether a file is a valid program. A firewall has to decide whether a packet matches a rule, and a search box has to find every match of a pattern. Formal languages make "valid syntax" and "pattern" precise: a language is a set of strings, a grammar generates it, and an automaton recognizes it. This chapter climbs a ladder of increasingly powerful machines (finite automata, pushdown automata, Turing machines) and ends at problems that no computer can solve at all.

<a id="131-languages-and-grammars"></a>

13.1 Languages and Grammars

This subchapter defines languages as sets of strings and grammars as finite sets of rewriting rules that generate them, then classifies grammars by how powerful their rules are.

Alphabets, Strings, and Languages

Why. Everything a program reads is a finite sequence of symbols: source code, a URL, a DNA sequence, a stream of bytes from a socket. To ask "which inputs are valid?" precisely, we need names for symbols, for sequences of symbols, and for sets of sequences. The payoff is large. One definition, "a language is a set of strings", covers syntax checking and pattern matching, and in 13.4 it covers every yes/no question a computer can be asked.

What.

• An alphabet Σ is a finite, non-empty set of symbols. Examples: {0, 1}, the ASCII characters, {A, C, G, T}, or the set of token types of a programming language.
• A string (or word) over Σ is a finite sequence of symbols from Σ (3.1). The empty string λ has no symbols (many books write ε). The length |w| is the number of symbols, so |λ| = 0 and |0110| = 4.
• Σⁿ is the set of strings of length exactly n, Σ* is the set of all strings, and Σ⁺ = Σ* − {λ} is the set of non-empty strings.
• A language over Σ is any subset L ⊆ Σ*.

Σ* has a recursive definition (3.3): λ ∈ Σ*, and if w ∈ Σ* and x ∈ Σ then wx ∈ Σ*. Proofs about all strings therefore use structural induction (3.3) or induction on |w| (3.2).

Operations on strings.

Operation	Notation	Example with u = ab, v = ba
Concatenation	uv	abba, and |uv| = |u| + |v|
Power	uⁿ = uu⋯u (n copies), u⁰ = λ	u³ = ababab
Reversal	uᴿ	(abb)ᴿ = bba
Prefix, suffix, substring	u is a prefix of uv, v a suffix, and y a substring of xyz	ab is a prefix of abba

Concatenation is associative and has identity λ, but it is not commutative. So (Σ*, ·, λ) is a monoid (12.1). It is called the free monoid on Σ, because no equations hold in it except those that associativity forces.

Languages are sets. Every set operation (2.1) applies to languages: union, intersection, and complement L̄ = Σ* − L. Three operations use the string structure:

Operation	Definition	Example with A = {0, 11}
Concatenation	AB = {xy : x ∈ A, y ∈ B}	A·{1} = {01, 111}
Power	A⁰ = {λ}, Aⁿ⁺¹ = AⁿA	A² = {00, 011, 110, 1111}
Kleene star	A* = A⁰ ∪ A¹ ∪ A² ∪ ⋯	A* = every string built from the blocks 0 and 11
Kleene plus	A⁺ = A¹ ∪ A² ∪ ⋯ = AA*	A* without λ (here, since λ ∉ A)

Two easily confused objects: ∅ is the language with no strings, and {λ} is the language containing only the empty string. They behave like 0 and 1: ∅L = ∅, {λ}L = L, and ∅* = {λ}.

Counting. If |Σ| = k, then |Σⁿ| = kⁿ (5.1), so Σ* is infinite but countable: the shortlex order of 2.3 lists it. The set of all languages, P(Σ*), is uncountable by Cantor's theorem (2.3). Programs are strings, so there are only countably many of them. Most languages therefore have no program that recognizes them, a fact that 13.4 makes concrete.

from itertools import product

def concat(A, B):
    return {x + y for x in A for y in B}

def power(A, n):
    result = {""}                                   # A⁰ = {λ}; Python's "" plays the role of λ
    for _ in range(n):
        result = concat(result, A)
    return result

def star(A, max_len):
    """The strings of A* with length <= max_len (A* itself is infinite)."""
    result, layer = {""}, {""}
    while layer:
        layer = {w for w in concat(layer, A) if len(w) <= max_len} - result
        result |= layer
    return result

shortlex = lambda w: (len(w), w)                    # by length, then alphabetically
A = {"0", "11"}
print(sorted(power(A, 2), key=shortlex))           # ['00', '011', '110', '1111']
print(sorted(star(A, 4), key=shortlex))
# ['', '0', '00', '11', '000', '011', '110', '0000', '0011', '0110', '1100', '1111']

# How many strings of each length are in A*? Tiling n cells with blocks of size 1 and 2: Fibonacci (3.3)
words = star(A, 12)
print([sum(len(w) == n for w in words) for n in range(13)])
# [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233]

# ∅ and {λ} behave like 0 and 1 under concatenation
print(concat(set(), A), concat({""}, A) == A)       # set() True

# |Σⁿ| = kⁿ: all 3-symbol strings over {a, b}
print(["".join(t) for t in product("ab", repeat=3)])
# ['aaa', 'aab', 'aba', 'abb', 'baa', 'bab', 'bba', 'bbb']

Analogy. An alphabet is a keyboard, a string is anything you can type on it, and a language is a rule for which typed texts are accepted, like a form field validator. The validator might accept infinitely many inputs, but it never sees an infinitely long one.

Key takeaways

• An alphabet is a finite set of symbols, a string is a finite sequence of them, and a language is any set of strings.
• λ is the empty string. ∅ (no strings) and {λ} (one empty string) are different languages.
• Concatenation makes Σ* a monoid with identity λ. It is associative but not commutative.
• Languages combine by union, intersection, complement, concatenation and Kleene star.
• Σ* is countable, but the set of languages is uncountable, so most languages have no recognizing program.

Practice

1. (Beginner) Let Σ = {a, b}. List every string in Σ⁰ ∪ Σ¹ ∪ Σ². How many strings of length at most n are there? Then compute ∅*, {λ}*, ∅ · {a} and {λ} · {a}.
2. (Intermediate) Prove that (uv)ᴿ = vᴿuᴿ for all strings u, v, by induction on |v|. Then decide whether A*B* = (A ∪ B)* for all languages A and B. Prove it or give a counterexample.
3. (Interview) Given a dictionary D of words and a string s with no spaces, decide whether s ∈ D*, that is, whether s can be split into dictionary words ("word break"). Hint: let ok[i] mean that the prefix s[:i] is in D*. Then ok[0] is true, and ok[i] holds if ok[j] holds and s[j:i] ∈ D for some j < i. How does the running time depend on |s| and on the length of the longest word?

Phrase-Structure Grammars

Why. Interesting languages are infinite, so they cannot be listed. We need a finite description that produces every string in the language and nothing else. Recursive definitions (3.3) do this for sets in general. A grammar is a recursive definition specialized to strings: a list of rewriting rules applied over and over, starting from a single symbol. Noam Chomsky introduced grammars in the 1950s to model natural language. Within a few years they were used to define the syntax of ALGOL, and since then of almost every programming language.

What. A phrase-structure grammar G = (V, T, S, P) consists of:

• a vocabulary V, a finite set of symbols;
• the terminals T ⊆ V, the symbols that appear in the final strings. The other symbols, N = V − T, are nonterminals: placeholders that still have to be rewritten;
• a start symbol S ∈ N;
• a finite set P of productions w₀ → w₁, where w₀, w₁ ∈ V* and w₀ contains at least one nonterminal.

By convention, nonterminals are uppercase letters, terminals are lowercase letters or digits, and A → α | β abbreviates the two productions A → α and A → β.

Derivations. If w₀ → w₁ is a production, then l w₀ r ⇒ l w₁ r for any strings l and r: replace one occurrence of the left side by the right side. Read ⇒ as "directly derives". ⇒* is its reflexive transitive closure (2.4): zero or more steps. The language generated by G is

  L(G) = { w ∈ T* : S ⇒* w }

that is, the strings of terminals only that can be derived from the start symbol. Intermediate strings that still contain nonterminals are called sentential forms.

Example 1: {aⁿbⁿ : n ≥ 0}. Take S → aSb | λ. Each use of the first production adds one a on the left and one b on the right, and the second ends the derivation:

  S ⇒ aSb ⇒ aaSbb ⇒ aaaSbbb ⇒ aaabbb

A proof that L(G) = {aⁿbⁿ} has two directions. ⊇: aⁿbⁿ is derived by using the first production n times. ⊆: by induction on the number of steps, every sentential form is aᵏSbᵏ or aᵏbᵏ.

Example 2: balanced parentheses. S → SS | (S) | λ generates (), (()), ()(), (()()) and so on: juxtapose two balanced strings, or wrap one in a pair of parentheses.

Example 3: {aⁿbⁿcⁿ : n ≥ 1}. Rules with a single nonterminal on the left cannot generate this language (13.3 and 13.4 explain why), but rules with longer left sides can:

  S → aSBC | aBC        generate aⁿ, then n copies of B and n copies of C in some order
  CB → BC               sort: move each B left past each C
  aB → ab   bB → bb     turn the Bs into bs, left to right
  bC → bc   cC → cc     then the Cs into cs

  S ⇒ aSBC ⇒ aaBCBC ⇒ aaBBCC ⇒ aabBCC ⇒ aabbCC ⇒ aabbcC ⇒ aabbcc

A derivation can also get stuck: from aaBCBC, applying aB → ab and then bC → bc gives aabcBC, and no rule can turn cB into anything. A stuck sentential form contributes nothing to L(G). Only derivations that reach a string of terminals count.

from collections import deque

def language(productions, start="S", max_len=6):
    """The words of L(G) with length <= max_len, by breadth-first search over sentential forms.
    Uppercase letters are nonterminals and "" is λ."""
    seen, queue, words = {start}, deque([start]), set()
    while queue:
        form = queue.popleft()
        if not any(ch.isupper() for ch in form):         # only terminals left: a word of L(G)
            words.add(form)
            continue
        for lhs, rhs in productions:
            i = form.find(lhs)
            while i != -1:                               # try rewriting each occurrence of lhs
                new = form[:i] + rhs + form[i + len(lhs):]
                if len(new) <= max_len + 1 and new not in seen:   # cap keeps the search finite;
                    seen.add(new)                        # +1 leaves room for one pending nonterminal
                    queue.append(new)
                i = form.find(lhs, i + 1)
    return sorted((w for w in words if len(w) <= max_len), key=lambda w: (len(w), w))

anbn = [("S", "aSb"), ("S", "")]
parens = [("S", "SS"), ("S", "(S)"), ("S", "")]
anbncn = [("S", "aSBC"), ("S", "aBC"), ("CB", "BC"),
          ("aB", "ab"), ("bB", "bb"), ("bC", "bc"), ("cC", "cc")]

print(language(anbn))                    # ['', 'ab', 'aabb', 'aaabbb']
print(language(parens))                  # ['', '()', '(())', '()()', '((()))', '(()())', '(())()', '()(())', '()()()']
print(language(anbncn, max_len=9))       # ['abc', 'aabbcc', 'aaabbbccc']

The length cap is a shortcut that works for these small grammars. In general, a derivation of a short word may pass through longer sentential forms, and 13.4 shows that no cap works for every grammar.

Analogy. A grammar is a set of search-and-replace macros together with a starting document. You may apply any macro anywhere, in any order. The language is every document you can reach that has no placeholders left.

Key takeaways

• A grammar (V, T, S, P) has terminals, nonterminals, a start symbol and productions w₀ → w₁.
• ⇒ rewrites one occurrence of a left side, and ⇒* is its reflexive transitive closure.
• L(G) contains the terminal-only strings derivable from S. Derivations that get stuck contribute nothing.
• Proving L(G) = L takes both directions: every string of L is derivable, and every derivable string is in L (usually by induction on the length of the derivation).
• Rules with a single nonterminal on the left are simple and common, but some languages need longer left sides.

Practice

1. (Beginner) Write a grammar for the palindromes over {a, b} and derive abbba. Then describe the language generated by S → aS | bA, A → bA | λ.
2. (Intermediate) Give a grammar for {aᵐbⁿ : m ≥ n ≥ 0} and prove that it generates exactly this language. Hint: separate the matched part aⁿbⁿ from the extra as, and induct on the length of the derivation.
3. (Interview) Prove that S → aSbS | bSaS | λ generates exactly the strings over {a, b} with equally many as and bs. Hint: the inclusion ⊆ follows by induction on the derivation. For ⊇, track the running difference #a − #b of a non-empty balanced word: it first returns to 0 at some position, which splits the word into a first block a…b or b…a and a balanced remainder.

Chomsky Hierarchy

Why. Allowing any rule makes grammars very powerful, but powerful grammars are hard to work with. Deciding whether a string can be derived may be slow, or impossible. Restricting the form of the productions trades power for efficient algorithms. Chomsky (1956) identified four nested levels, and each corresponds to a kind of machine studied later in this chapter. This is why a compiler uses regular expressions for tokens and a context-free grammar for syntax, rather than one formalism for everything.

What. The types restrict the productions w₀ → w₁:

Type	Name	Allowed productions	Recognizing machine	Typical language
0	Unrestricted	Any w₀ → w₁ (with a nonterminal in w₀)	Turing machine (13.4)	Recursively enumerable: {⟨M⟩ : M halts}
1	Context-sensitive	|w₀| ≤ |w₁| (non-contracting), plus S → λ if S is on no right side	Linear-bounded automaton	{aⁿbⁿcⁿ}
2	Context-free	A → w₁: a single nonterminal on the left	Pushdown automaton (13.4)	{aⁿbⁿ}, balanced parentheses, arithmetic expressions
3	Regular	A → aB, A → a, and S → λ	Finite automaton (13.2)	a*b*, identifiers, numbers

"Context-free" means a nonterminal A can be rewritten wherever it appears, regardless of its neighbours. A context-sensitive rule such as aB → ab rewrites B only in the context of an a on its left. The standard definition of type 1 is in exactly this form, lAr → lwr with w ≠ λ. It generates the same languages as non-contracting rules, which are easier to check.

A language has type k if some grammar of type k generates it. {aⁿbⁿ} is generated by a type 0 grammar too, but it is called context-free because a type 2 grammar exists for it, and not regular because no type 3 grammar does (13.3 proves this).

  ┌──────────────────────────────────────────────────────────────┐
  │ All languages over Σ  (uncountably many)                     │
  │  ┌────────────────────────────────────────────────────────┐  │
  │  │ Type 0: recursively enumerable     e.g. HALT (13.4)    │  │
  │  │  ┌──────────────────────────────────────────────────┐  │  │
  │  │  │ Type 1: context-sensitive      e.g. aⁿbⁿcⁿ       │  │  │
  │  │  │  ┌────────────────────────────────────────────┐  │  │  │
  │  │  │  │ Type 2: context-free       e.g. aⁿbⁿ       │  │  │  │
  │  │  │  │  ┌──────────────────────────────────────┐  │  │  │  │
  │  │  │  │  │ Type 3: regular        e.g. a*b*     │  │  │  │  │
  │  │  │  │  └──────────────────────────────────────┘  │  │  │  │
  │  │  │  └────────────────────────────────────────────┘  │  │  │
  │  │  └──────────────────────────────────────────────────┘  │  │
  │  └────────────────────────────────────────────────────────┘  │
  └──────────────────────────────────────────────────────────────┘

Every inclusion is strict, and the example in each ring lies outside the ring inside it. Strictly between types 1 and 0 lie the decidable languages that are not context-sensitive. Outside type 0 lie languages that no grammar generates at all, such as the complement of the halting problem (13.4).

Grammars versus languages. As sets of grammars, the types are almost nested: a regular grammar is context-free, and a context-free grammar without λ-productions is non-contracting. A context-free rule like A → λ breaks the inclusion between types 1 and 2, but every context-free language has a grammar whose only λ-production is S → λ. So the language classes are properly nested, as in the diagram.

What each level costs. Membership, the question "is w ∈ L(G)?" for |w| = n, gets harder with each step up:

Type	Membership test	Cost
3	Run a DFA (13.2)	O(n) time, O(1) memory
2	CYK or Earley parsing. LL and LR parsers for restricted grammars	O(n³) in general, O(n) for LL/LR
1	Search over sentential forms of length at most n	Decidable, but PSPACE-complete in general
0	Search over all derivations	Only semi-decidable: a "yes" is eventually confirmed, a "no" may never be (13.4)

def grammar_type(productions, start="S"):
    """The most restrictive Chomsky type (3, 2, 1 or 0) that a grammar satisfies.
    Uppercase letters are nonterminals, lowercase letters are terminals, "" is λ."""
    single_nt = lambda s: len(s) == 1 and s.isupper()
    if all(single_nt(l) and (r == "" and l == start                         # S → λ
                             or len(r) == 1 and r.islower()                 # A → a
                             or len(r) == 2 and r[0].islower() and r[1].isupper())   # A → aB
           for l, r in productions):
        return 3
    if all(single_nt(l) for l, r in productions):
        return 2
    start_on_right = any(start in r for l, r in productions)
    if all(len(l) <= len(r) or (l == start and r == "" and not start_on_right)
           for l, r in productions):
        return 1
    return 0

grammars = {
    "a*b":    [("S", "aS"), ("S", "b")],
    "aⁿbⁿ":   [("S", "aSb"), ("S", "")],
    "aⁿbⁿcⁿ": [("S", "aSBC"), ("S", "aBC"), ("CB", "BC"), ("aB", "ab"),
               ("bB", "bb"), ("bC", "bc"), ("cC", "cc")],
    "erasing": [("S", "aSb"), ("S", "X"), ("aXb", "")],          # aXb → λ shrinks the form
}
for name, P in grammars.items():
    print(f"{name:8} type {grammar_type(P)}")
# a*b      type 3
# aⁿbⁿ     type 2
# aⁿbⁿcⁿ   type 1
# erasing  type 0

In compilers. A front end uses each level for the job it fits. The lexer groups characters into tokens (identifiers, numbers, keywords) using regular expressions compiled to DFAs (type 3). The parser checks nesting and structure using a context-free grammar (type 2). Rules like "a variable must be declared before it is used" or "a call has as many arguments as the function has parameters" are not context-free, so semantic analysis checks them in ordinary code, with a symbol table.

Key takeaways

• Type 3 (regular) ⊂ type 2 (context-free) ⊂ type 1 (context-sensitive) ⊂ type 0 (unrestricted) as language classes, and every inclusion is strict.
• Each type matches a machine: finite automaton, pushdown automaton, linear-bounded automaton, Turing machine.
• A language's type is that of the most restrictive grammar that generates it, not that of a particular grammar.
• More power makes membership more expensive: linear for regular, cubic for context-free, undecidable for type 0.
• Compilers use regular languages for tokens, context-free grammars for syntax, and ordinary code for context-dependent rules.

Practice

1. (Beginner) Find the most restrictive type of each grammar: (a) S → 0S | 1S | 0; (b) S → 0S1 | 01; (c) S → AB, AB → BA, A → a, B → b; (d) S → aA, A → Sb | b. Then decide whether the language of (d) has a smaller type than the grammar.
2. (Intermediate) Place each language in the smallest class that contains it, and give a one-line reason: {a²ⁿ : n ≥ 0}, {aⁿbⁿ : n ≥ 0}, {aⁿbⁿcⁿ : n ≥ 0}, {aⁿ : n is prime}, {wcw : w ∈ {a, b}*}.
3. (Interview) Why do compilers use a separate lexer instead of writing one grammar that goes all the way down to characters? Where in the hierarchy does "every variable is declared before use" belong, and how do compilers enforce it? Hint: compare the cost of a DFA with the cost of general parsing, and consider which tokens a parser needs one symbol of lookahead to tell apart. For declarations, compare the language {wcw}.

Backus–Naur Form

Why. A programming language needs a syntax definition that people can read and that parser generators can process. Writing productions as S → aSb works for textbooks, but real grammars have dozens of nonterminals with meaningful names. The ALGOL 60 report (1960) introduced the notation that is still used today, due to John Backus and Peter Naur. Language standards (C, Java, SQL), internet protocols (RFC grammars) and data formats (JSON) are all specified this way.

What. Backus–Naur form (BNF) is a notation for context-free grammars:

• nonterminals are names in angle brackets, such as <expr>;
• ::= replaces →, and | separates alternatives;
• terminals are written literally, or quoted.

Extended BNF (EBNF) adds shorthands that make grammars shorter but no more powerful. Each one can be translated back into plain BNF with a fresh nonterminal:

EBNF	Meaning	Plain BNF
[ x ] or x?	Optional	<A> ::= x | λ
{ x } or x*	Zero or more	<A> ::= <A> x | λ
x+	One or more	<A> ::= <A> x | x
( x | y )	Grouping	<A> ::= x | y

Common variants are ISO EBNF (= and ,), ABNF in internet RFCs, and the PEG grammar of Python's own parser.

Example: arithmetic with precedence. Precedence and associativity can be built into the grammar itself, with one nonterminal per precedence level:

  <expr>   ::= <expr> "+" <term>   | <expr> "-" <term>   | <term>
  <term>   ::= <term> "*" <factor> | <term> "/" <factor> | <factor>
  <factor> ::= "(" <expr> ")" | <number>
  <number> ::= <digit> | <number> <digit>
  <digit>  ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

• * binds tighter than + because a <term> sits below an <expr>: a sum is made of products, never the other way round without parentheses.
• <expr> ::= <expr> "-" <term> is left-recursive, so 8 - 3 - 2 groups as (8 - 3) - 2, which is left associativity.

The same grammar in EBNF replaces the left recursion with repetition:

  expr   = term   { ("+" | "-") term } ;
  term   = factor { ("*" | "/") factor } ;
  factor = "(" expr ")" | number ;
  number = digit { digit } ;

From EBNF to a parser. A recursive-descent parser has one function per nonterminal. Each alternative becomes an if, and each { … } becomes a while loop. The left-recursive BNF rule cannot be translated literally, because expr() would call expr() before consuming any input and recurse forever. The EBNF loop fixes this and still combines terms from the left, so - stays left-associative.

import re

def evaluate(text):
    """Recursive-descent parser and evaluator for the EBNF grammar above."""
    tokens = re.findall(r"\d+|[-+*/()]", text)     # the lexer: a regular language (13.3)
    if "".join(tokens) != re.sub(r"\s+", "", text):
        raise SyntaxError(f"bad character in {text!r}")
    pos = 0

    def peek():
        return tokens[pos] if pos < len(tokens) else None

    def eat(expected=None):
        nonlocal pos
        tok = peek()
        if tok is None or (expected and tok != expected):
            raise SyntaxError(f"expected {expected or 'a token'} at position {pos}, got {tok}")
        pos += 1
        return tok

    def expr():                                    # expr = term { ("+" | "-") term }
        value = term()
        while peek() in ("+", "-"):
            op = eat()
            rhs = term()
            value = value + rhs if op == "+" else value - rhs   # combine left to right
        return value

    def term():                                    # term = factor { ("*" | "/") factor }
        value = factor()
        while peek() in ("*", "/"):
            op = eat()
            rhs = factor()
            value = value * rhs if op == "*" else value / rhs
        return value

    def factor():                                  # factor = "(" expr ")" | number
        if peek() == "(":
            eat("(")
            value = expr()
            eat(")")
            return value
        tok = eat()
        if not tok.isdigit():
            raise SyntaxError(f"expected a number at position {pos - 1}, got {tok}")
        return int(tok)

    value = expr()
    if peek() is not None:
        raise SyntaxError(f"unexpected {peek()} at position {pos}")
    return value

print(evaluate("2 * (3 + 4) - 5"))   # 9
print(evaluate("8 - 3 - 2"))         # 3: left-associative, (8 - 3) - 2
print(evaluate("2 + 3 * 4"))         # 14: * binds tighter than +
try:
    evaluate("2 + * 3")
except SyntaxError as e:
    print(e)                         # expected a number at position 2, got *

Analogy. BNF is a recipe card: "a sandwich is bread, filling, bread; a filling is cheese, or ham, or a filling followed by a filling". Each name on the card is defined on the card, and the parser is a cook who follows it top-down.

Key takeaways

• BNF writes context-free productions as <A> ::= α | β. EBNF adds optional parts, repetition and grouping without adding power.
• One nonterminal per precedence level builds precedence into the grammar. Left recursion gives left associativity, and right recursion gives right associativity.
• Recursive-descent parsers translate EBNF directly: one function per nonterminal, a loop for each { … }.
• Left-recursive rules make recursive descent loop forever. Rewrite them as repetition, or remove the left recursion.

Practice

1. (Beginner) Write BNF for signed decimal integers: an optional + or -, then digits with no leading zeros (but 0 itself allowed). Which of -0, 007, +42 does your grammar accept?
2. (Intermediate) Add a right-associative exponent operator ^ that binds tighter than *, so that 2 ^ 3 ^ 2 = 2 ^ 9 = 512. Update the BNF, the EBNF and evaluate. Hint: power ::= factor "^" power | factor uses right recursion, which recursive descent handles without trouble.
3. (Interview) A recursive-descent parser for <A> ::= <A> "x" | "y" crashes with a stack overflow. Explain why, and transform the grammar so that it generates the same language without left recursion. Hint: the language is y x*. In general A → Aα | β becomes A → βA', A' → αA' | λ. Think about what happens to associativity, and how a loop recovers it.

Derivation Trees

Why. A derivation is a sequence of steps, but the order in which independent nonterminals are rewritten does not matter. What matters is the structure: which parts of the string were grouped together. A derivation tree records exactly that structure. Compilers build one for every program, because the tree is the meaning: 1 + 2 * 3 is either 1 + (2 * 3) = 7 or (1 + 2) * 3 = 9, depending on the tree.

What. For a context-free grammar, a derivation tree (or parse tree) is an ordered rooted tree (9.1) such that:

• the root is labeled with the start symbol;
• each internal vertex is labeled with a nonterminal A, and its children, read left to right, are labeled with the symbols of the right side of a production A → X₁X₂⋯Xₖ (one child labeled λ for A → λ);
• each leaf is labeled with a terminal or with λ.

The yield of the tree is the sequence of leaf labels read left to right, which is the derived string.

A leftmost derivation always rewrites the leftmost nonterminal, and a rightmost derivation always rewrites the rightmost one. Each parse tree corresponds to exactly one leftmost derivation (a preorder traversal of its internal vertices, 9.3) and exactly one rightmost derivation. So "two different trees" and "two different leftmost derivations" mean the same thing.

Ambiguity. A grammar is ambiguous if some string has two different parse trees. Consider E → E + E | E * E | ( E ) | a. The string a + a * a has two trees:

           E                               E
        /  |  \                         /  |  \
       E   +   E                       E   *   E
       |     / | \                   / | \     |
       a    E  *  E                 E  +  E    a
            |     |                 |     |
            a     a                 a     a

    a + (a * a): the * is deeper,    (a + a) * a: the + is deeper,
    so it is evaluated first         so it is evaluated first

The unambiguous grammar of the previous topic, with <expr>, <term> and <factor>, generates the same strings but allows only the left tree. In general, ambiguity is removed by layering the grammar by precedence and making each layer recursive on one side only.

Some context-free languages are inherently ambiguous: every grammar for them is ambiguous. The standard example is {aⁱbʲcᵏ : i = j or j = k}, because strings aⁿbⁿcⁿ belong to both parts. Whether a context-free grammar is ambiguous is undecidable (13.4), so there is no general tool that checks it.

The dangling else. In if a then if b then s1 else s2, the else can belong to either if. Most languages resolve the ambiguity with a side rule ("an else matches the nearest unmatched if"). Python avoids it with indentation, and C-family style guides recommend braces.

Counting parse trees. With the ambiguous grammar, an expression with n operators has one parse tree per way of choosing the "last" operator at the root and then recursively bracketing each side. That is the recurrence of the Catalan numbers (5.6), so the count is Cₙ = 1, 1, 2, 5, 14, 42, …, which grows exponentially.

from functools import lru_cache

def parse_trees(tokens):
    """All parse trees of E → E + E | E * E | num, as fully parenthesized strings."""
    @lru_cache(maxsize=None)
    def trees(i, j):                         # trees whose yield is tokens[i:j]
        if j - i == 1:
            return (tokens[i],)              # a single number: E → num
        result = []
        for k in range(i + 1, j - 1, 2):     # tokens[k] is the operator at the root
            for left in trees(i, k):
                for right in trees(k + 1, j):
                    result.append(f"({left}{tokens[k]}{right})")
        return tuple(result)
    return trees(0, len(tokens))

for tree in parse_trees(("1", "+", "2", "*", "3")):
    print(tree, "=", eval(tree))
# (1+(2*3)) = 7
# ((1+2)*3) = 9

print([len(parse_trees(("1",) + ("+", "1") * n)) for n in range(8)])
# [1, 1, 2, 5, 14, 42, 132, 429]: the Catalan numbers (5.6)

From parse tree to syntax tree. A parse tree contains every nonterminal, including chains like <expr> → <term> → <factor> → <number>. Compilers usually keep a compressed abstract syntax tree (AST), with operators at the internal vertices and operands at the leaves. This is the expression tree of 9.3. Its postorder traversal is the postfix code that a stack machine executes.

Analogy. A parse tree is the sentence diagram from grammar class. "I saw the man with the telescope" has two diagrams: either I used the telescope, or the man had it. An ambiguous grammar is a grammar for which such sentences exist.

Key takeaways

• A parse tree has the start symbol at the root, one production at each internal vertex and terminals at the leaves. Its yield is the derived string.
• Parse trees correspond one-to-one to leftmost derivations, and to rightmost derivations.
• A grammar is ambiguous if some string has two parse trees. For expressions, that means two meanings.
• Ambiguity is removed by layering by precedence. Some languages are inherently ambiguous, and ambiguity of a grammar is undecidable.
• The naive expression grammar gives a Catalan number of parse trees per expression.

Practice

1. (Beginner) Draw the parse tree of a * (a + a) in the grammar <expr>, <term>, <factor> of the previous topic (with a as a <factor>). Write out its leftmost and its rightmost derivation.
2. (Intermediate) Show that S → SS | (S) | λ is ambiguous by finding two parse trees for ()(). Then prove that S → (S)S | λ generates the same language unambiguously. Hint: in a non-empty balanced string, the first ( has a unique matching ).
3. (Interview) Explain the dangling-else problem in if a then if b then s1 else s2. How do parser generators such as yacc resolve it by default, and how can the grammar itself be fixed? Hint: the parser sees a shift/reduce conflict when it reaches else, and preferring "shift" attaches the else to the nearest if. A grammar fix splits statements into "matched" ones (every if has an else) and "unmatched" ones.

<a id="132-finite-state-machines"></a>

13.2 Finite-State Machines

This subchapter studies machines with a fixed, finite memory. It starts with machines that produce output, then moves to automata that only accept or reject, and ends with the algorithms that convert automata into deterministic form and shrink them to their minimal size.

Finite-State Machines with Output

Why. A vending machine, a traffic light, a network protocol handler and a serial adder all react to a stream of inputs, and each reaction depends on the input and on a bounded summary of the past. The vending machine does not remember every coin ever inserted, only the credit so far. That summary is the state. Modeling a system as a finite set of states with explicit transitions makes every possible behavior visible, so it can be tested exhaustively and implemented directly in hardware: sequential circuits (11.2) are finite-state machines built from gates and flip-flops.

What. A finite-state machine with output (a Mealy machine) is M = (S, I, O, f, g, s₀) where:

• S is a finite set of states and s₀ ∈ S is the start state;
• I is the input alphabet and O the output alphabet;
• f: S × I → S is the transition function: the next state;
• g: S × I → O is the output function: the output produced on that transition.

Reading the input x₁x₂⋯xₙ, the machine visits s₀, s₁, …, sₙ with sₖ = f(sₖ₋₁, xₖ), and emits g(sₖ₋₁, xₖ) at each step. The machine is given by a state table (one row per state, one column per input) or by a state diagram: a directed graph (8.1) with an edge s → f(s, x) labeled x / g(s, x).

In a Moore machine, the output depends only on the current state, through h: S → O. The two models are equally expressive. Converting Mealy to Moore may multiply the number of states, because each state must also remember the last output, and a Moore machine produces one extra output for the start state.

	Mealy	Moore
Output depends on	State and current input	State only
Output written on	Edges: x / y	States
Reacts to an input	In the same step	One step later
Number of states	Often fewer	Possibly more
Hardware	Outputs are combinational in the inputs	Outputs come straight from registers, which avoids glitches

Example: a serial binary adder. Add two binary numbers fed in one bit pair at a time, least significant bit first. The only thing to remember between steps is the carry, so two states suffice: s₀ (carry 0) and s₁ (carry 1). On input (x, y) in state sᶜ, the machine outputs (x + y + c) mod 2 and moves to the state for carry ⌊(x + y + c)/2⌋.

State	00	01	10	11
s₀ (carry 0)	s₀, out 0	s₀, out 1	s₀, out 1	s₁, out 0
s₁ (carry 1)	s₀, out 1	s₁, out 0	s₁, out 0	s₁, out 1

                       11 / 0
          ┌───────────────────────────────┐
          │                               ▼
  ──▶   ( s₀ )                          ( s₁ )
        carry 0                         carry 1
          ▲                               │
          └───────────────────────────────┘
                       00 / 1

  self-loops:  s₀ on 00/0, 01/1, 10/1          s₁ on 01/0, 10/0, 11/1

One full adder (11.2) plus one flip-flop that stores the carry is exactly this machine in hardware. It adds numbers of any length with constant hardware, at one bit per clock tick.

def run_mealy(f, g, start, inputs):
    """Run a Mealy machine: f gives the next state and g the output, both keyed by (state, input)."""
    state, outputs = start, []
    for x in inputs:
        outputs.append(g[state, x])
        state = f[state, x]
    return outputs

# Serial adder: the state is the carry, the input is a pair of bits
bit_pairs = [(x, y) for x in (0, 1) for y in (0, 1)]
f = {(c, (x, y)): (x + y + c) // 2 for c in (0, 1) for x, y in bit_pairs}   # next carry
g = {(c, (x, y)): (x + y + c) % 2 for c in (0, 1) for x, y in bit_pairs}    # sum bit

def serial_add(a, b):
    n = max(a.bit_length(), b.bit_length()) + 1                 # one extra step to flush the carry
    pairs = [((a >> i) & 1, (b >> i) & 1) for i in range(n)]    # least significant bit first
    out = run_mealy(f, g, 0, pairs)
    return sum(bit << i for i, bit in enumerate(out)), pairs, out

total, pairs, out = serial_add(13, 11)
print(pairs)    # [(1, 1), (0, 1), (1, 0), (1, 1), (0, 0)]
print(out)      # [0, 0, 0, 1, 1]: 11000 read backwards
print(total)    # 24

print(all(serial_add(a, b)[0] == a + b for a in range(256) for b in range(256)))   # True

What finite memory cannot do. A machine with k states can only distinguish k different histories. So no finite-state machine can output, after each input, whether it has seen more 0s than 1s so far. Telling apart the histories 0, 00, 000, … would need infinitely many states. 13.3 turns this observation into a proof technique, and 13.4 adds unbounded memory.

Analogy. A finite-state machine is a turnstile. It is either locked or unlocked. A coin unlocks it, a push while unlocked lets you through and locks it again, and a push while locked does nothing. The turnstile does not count coins or people. Its whole history is summarized by one of two states.

Key takeaways

• A Mealy machine (S, I, O, f, g, s₀) has a transition function and an output function, both depending on the state and the input.
• A Moore machine attaches outputs to states. The two models are equivalent, but a Moore machine may need more states.
• The state is the bounded summary of the past that the future behavior depends on.
• State tables and state diagrams describe the machine completely, which makes exhaustive testing possible.
• Finite memory cannot count without bound. That limitation drives the rest of this chapter.

Practice

1. (Beginner) Design a Mealy machine with input and output alphabet {0, 1} that outputs 1 exactly when the last three inputs were all 1. Give its state table and its output on 0111101111.
2. (Intermediate) Convert the serial adder into a Moore machine whose state output is the most recent sum bit. How many states does it need? Hint: a state must record both the carry and the last sum bit.
3. (Interview) You are implementing the life cycle of an order in a web shop: created, paid, shipped, delivered, cancelled and refunded, with rules such as "cannot ship before payment" and "cannot cancel after delivery". How would you structure the code so that an invalid transition cannot happen silently, and how would you test it? Hint: use an explicit transition table keyed by (state, event) and treat a missing key as an error. With finitely many states and events, a test can enumerate every pair.

Deterministic Finite Automata

Why. Many questions about input are plain yes/no questions. Is this a valid identifier? Does this packet match the rule? Is this binary number divisible by 3? Dropping the output of a finite-state machine and marking some states as "accepting" gives a recognizer that answers such questions with one table lookup per input symbol and constant memory. Nothing runs faster: the input has to be read anyway.

What. A deterministic finite automaton (DFA) is M = (S, I, f, s₀, F) where:

• S is a finite set of states, s₀ ∈ S the start state, and F ⊆ S the set of accepting (final) states;
• I is the input alphabet;
• f: S × I → S is the transition function. Every state has exactly one transition for every symbol, which is what "deterministic" means.

Many books write (Q, Σ, δ, q₀, F) for the same five components. The extended transition function follows a whole string, by recursion on its length (3.3):

  f*(s, λ)  = s
  f*(s, wa) = f(f*(s, w), a)        for w ∈ I*, a ∈ I

M accepts w if f*(s₀, w) ∈ F, and rejects it otherwise. The language recognized by M is L(M) = {w ∈ I* : M accepts w}. Two automata are equivalent if they recognize the same language.

In diagrams, the start state has an incoming arrow from nowhere and accepting states are drawn with a double circle, written ((s)) below. Diagrams often omit transitions. The missing ones go to an implicit dead state (or trap state): a non-accepting state that loops to itself on every symbol.

Example: binary numbers divisible by 3. Reading a bit b after a prefix with value v gives the value 2v + b. Divisibility only depends on the value mod 3 (4.3), so it suffices to remember r = v mod 3, and the new remainder is (2r + b) mod 3:

State r	On 0	On 1
→ ((0))	0	1
1	2	0
2	1	2

                 1                 0
         ┌───────────────┐ ┌───────────────┐
         │               ▼ │               ▼
  ──▶  ((0))            ( 1 )            ( 2 )
         ▲               │ ▲               │
         └───────────────┘ └───────────────┘
                 1                 0

  self-loops: 0 on input 0,  2 on input 1

Reading 1001 (nine): 0 →¹ 1 →⁰ 2 →⁰ 1 →¹ 0. The run ends in 0, so the string is accepted.

Designing a DFA. Ask: "what is the least I must remember about the prefix read so far to decide the rest?" Each state is one possible answer, and you should be able to state it as an invariant: "the automaton is in state r exactly when the prefix has value ≡ r (mod 3)". Correctness is then a proof by induction on the length of the input (3.2). The base case is the start state on λ, and the inductive step checks every transition.

class DFA:
    def __init__(self, f, start, accept):
        self.f, self.start, self.accept = f, start, set(accept)

    def run(self, w):
        state = self.start
        for ch in w:
            state = self.f[state, ch]      # one table lookup per symbol: O(|w|) time, O(1) memory
        return state

    def accepts(self, w):
        return self.run(w) in self.accept

def mod_dfa(k, base=2):
    """Accepts the base-b numerals divisible by k. The state is the value of the prefix mod k."""
    digits = "0123456789"[:base]
    f = {(r, d): (base * r + int(d)) % k for r in range(k) for d in digits}
    return DFA(f, start=0, accept={0})

div3 = mod_dfa(3)
print([div3.run(p) for p in ["", "1", "10", "100", "1001"]])   # [0, 1, 2, 1, 0]
print(div3.accepts("1001"), div3.accepts("1011"))              # True False  (9 and 11)

# Invariant check: the DFA accepts bin(n) exactly when 3 divides n
print(all(div3.accepts(format(n, "b")) == (n % 3 == 0) for n in range(10_000)))   # True

# The same construction for decimal input: divisibility by 7 with O(1) memory
div7 = mod_dfa(7, base=10)
print(div7.accepts("123456789123456789"), 123456789123456789 % 7 == 0)   # True True
print(div7.accepts("1000000007"), 1000000007 % 7 == 0)                   # False False
print(div7.accepts("700000000000000000014"))                             # True

Where DFAs run. Lexers (flex, the tokenizers of most compilers), network packet classifiers, protocol parsers, hardware controllers, string search (Knuth–Morris–Pratt builds a DFA for the pattern) and input validation. Their cost is O(n) time for an input of length n and |S| · |I| table entries.

Analogy. A DFA is a board game with a single pawn. Each input symbol is a card that says "from this square, move to that square". You play the cards in order, and you win if the pawn ends on a gold square. There are no choices to make: the cards decide every move.

Key takeaways

• A DFA (S, I, f, s₀, F) has exactly one transition per state and symbol. It accepts w if f*(s₀, w) ∈ F.
• Missing transitions in diagrams go to an implicit dead state.
• Design a DFA by asking what must be remembered about the prefix, and prove it correct with a state invariant and induction.
• Running a DFA takes O(n) time and O(1) memory, which makes DFAs the fastest possible recognizers.
• Divisibility by k in any base needs only k states, because only the remainder matters.

Practice

1. (Beginner) Design a DFA over {0, 1} that accepts the strings with an even number of 0s and an even number of 1s. Hint: 4 states, one for each pair of parities.
2. (Intermediate) Design a DFA over {a, b} that accepts the strings that do not contain abb as a substring. Write down the invariant of each state and prove that the automaton is correct.
3. (Interview) A stream of decimal digits, too long to store, arrives one digit at a time. At the end you must report whether the number is divisible by 7, and also whether it is divisible by 6. What state do you keep? Hint: the remainder r updates to (10r + d) mod k. For 6 you can keep the remainder mod 6, or combine the remainders mod 2 and mod 3, which is a product of two automata (13.3).

Nondeterministic Finite Automata

Why. Some languages are easy to describe by guessing. "The third symbol from the end is 1": a DFA has to remember the last three symbols at all times, because it does not know when the input will end. A machine that is allowed to guess "this 1 is the third from the end" and then check the guess needs only four states. Nondeterminism also makes automata easy to combine: gluing machines together for "this or that" or "this, then that" is natural when a machine may follow several paths at once. The next topic shows that this convenience adds no power. Every nondeterministic automaton can be converted into a deterministic one.

What. A nondeterministic finite automaton (NFA) is M = (S, I, f, s₀, F) like a DFA, except that the transition function returns a set of states:

  f: S × I → P(S)        (P(S) is the power set of S, 2.1)

From a state, a symbol can lead to several states or to none. M accepts w if some sequence of choices reads w and ends in an accepting state. It rejects w only if every possible path either gets stuck or ends in a non-accepting state.

Many definitions also allow λ-transitions: edges that the machine may follow without reading a symbol. The λ-closure of a set of states T is the set of states reachable from T using λ-transitions only. λ-transitions make constructions easier (Kleene's theorem, 13.3) but do not add power.

There are three equivalent ways to think about acceptance:

View	How the NFA processes w	Accepts when
Lucky guesser	An oracle picks the right transition at each step	A correct choice exists
Parallel threads	At each choice, the machine clones itself and the clones go different ways	At least one clone ends in F
Set of states	Track the set T of all states reachable after each prefix	The final T meets F

The third view is the algorithm. It never backtracks, and it costs O(|w| · |S|²) time in the worst case.

Example: the third symbol from the end is 1.

         0, 1
         ┌──┐
         │  ▼
  ──▶   ( q0 ) ──1──▶ ( q1 ) ──0,1──▶ ( q2 ) ──0,1──▶ ((q3))

q0 reads the input and, on a 1, may guess "this is the third symbol from the end". q1, q2 and q3 then count the two remaining symbols. If the guess was wrong, that thread either gets stuck at q3 (more input follows, and q3 has no transitions) or ends in a non-accepting state. Tracking the sets on input 0110:

Read so far	Set of current states
λ	{q0}
0	{q0}
01	{q0, q1}
011	{q0, q1, q2}
0110	{q0, q2, q3}, which contains q3: accept

from itertools import product

def nfa_run(f, start, accept, w):
    """Simulate an NFA by tracking the set of current states.
    f maps (state, symbol) to a set of states. The symbol "" marks a λ-transition."""
    def closure(states):                             # add everything reachable by λ-moves
        stack, result = list(states), set(states)
        while stack:
            for t in f.get((stack.pop(), ""), ()):
                if t not in result:
                    result.add(t)
                    stack.append(t)
        return result

    current = closure({start})
    trace = [sorted(current)]
    for ch in w:
        current = closure({t for s in current for t in f.get((s, ch), ())})
        trace.append(sorted(current))
    return bool(current & accept), trace

# Third symbol from the end is 1
third = {("q0", "0"): {"q0"}, ("q0", "1"): {"q0", "q1"},
         ("q1", "0"): {"q2"}, ("q1", "1"): {"q2"},
         ("q2", "0"): {"q3"}, ("q2", "1"): {"q3"}}
ok, trace = nfa_run(third, "q0", {"q3"}, "0110")
print(ok, trace)
# True [['q0'], ['q0'], ['q0', 'q1'], ['q0', 'q1', 'q2'], ['q0', 'q2', 'q3']]

all_strings = ("".join(t) for n in range(10) for t in product("01", repeat=n))
print(all(nfa_run(third, "q0", {"q3"}, w)[0] == (len(w) >= 3 and w[-3] == "1")
          for w in all_strings))                       # True

# λ-transitions: a*b* as "read a's in p, then jump (for free) to q and read b's"
ab = {("p", "a"): {"p"}, ("p", ""): {"q"}, ("q", "b"): {"q"}}
print([nfa_run(ab, "p", {"q"}, w)[0] for w in ["", "aab", "abb", "aba", "ba"]])
# [True, True, True, False, False]

Simulation versus backtracking. A program can also simulate an NFA by trying one path at a time and backtracking when it fails. That works, but the number of paths can grow exponentially with the input length. Tracking the set of states visits each (position, state) pair at most once. Regular expression engines are split along exactly this line (13.3): grep, RE2 and the Rust regex crate track sets of states, while the engines of Perl, Python, Java and JavaScript backtrack.

Analogy. An NFA is a maze explored by a crowd. At every fork, the crowd splits and sends people down every branch. People who hit a dead end leave. You do not care who made it, only whether anyone is standing at an exit when the input runs out.

Key takeaways

• An NFA's transition function returns a set of states, possibly empty. λ-transitions consume no input.
• An NFA accepts if some path ends in an accepting state, and rejects only if all paths fail.
• Simulate an NFA by tracking the set of reachable states, with λ-closure after each step. This takes polynomial time with no backtracking.
• NFAs are often much smaller than equivalent DFAs: 4 states versus 8 for "third symbol from the end".
• Nondeterminism adds convenience, not power. The next topic converts any NFA into a DFA.

Practice

1. (Beginner) Draw an NFA over {0, 1} that accepts the strings containing 0101 as a substring. Track the set of states on input 1010110.
2. (Intermediate) Show how to remove λ-transitions from an NFA without adding states. Hint: define f'(s, a) as the λ-closure of all states reachable from the λ-closure of s by one a-transition, and make s accepting if its λ-closure contains an accepting state.
3. (Interview) Implement filename matching for glob patterns with ? (any one character) and * (any sequence of characters) so that it runs in O(|pattern| · |name|) time, even for patterns like *a*a*a*a*b. Hint: make one NFA state per pattern position. A * state loops to itself on every character and also has a λ-transition to the next state. Then track sets of states instead of backtracking.

NFA to DFA Conversion

Why. NFAs are easy to build and DFAs are fast to run. Fortunately, you can always have both: build the NFA and convert it mechanically into an equivalent DFA. The conversion also proves that nondeterminism adds no power to finite automata. This is not true for every model: for pushdown automata (13.4) nondeterminism really does add power. Lexer generators and regex compilers do this conversion every time they compile a pattern.

What. The subset construction (Rabin and Scott, 1959) turns the "set of states" simulation into a DFA. Given an NFA N = (S, I, f, s₀, F) without λ-transitions, define the DFA D by:

DFA component	Definition
States	Subsets T ⊆ S. Only those reachable from the start are built
Start state	{s₀}
Transition	f_D(T, a) = ⋃_{s ∈ T} f(s, a)
Accepting states	Subsets T with T ∩ F ≠ ∅

With λ-transitions, use the λ-closure of {s₀} as the start state and the λ-closure of each union as the transition. The empty set is a valid DFA state: it is the dead state.

Correctness. By induction on |w|, f_D*({s₀}, w) is exactly the set of NFA states reachable from s₀ by reading w. So D accepts w ⇔ that set contains an accepting state ⇔ some path of N accepts w.

Worked example. Converting the "third symbol from the end is 1" NFA (states 0, 1, 2, 3 for q0, …, q3) gives these reachable subsets. Each one always contains 0, plus a record of which of the last three symbols were 1:

DFA state	On 0	On 1	Accepting	Last three symbols
→ {0}	{0}	{0,1}		000
{0,1}	{0,2}	{0,1,2}		001
{0,2}	{0,3}	{0,1,3}		010
{0,1,2}	{0,2,3}	{0,1,2,3}		011
{0,3}	{0}	{0,1}	yes	100
{0,1,3}	{0,2}	{0,1,2}	yes	101
{0,2,3}	{0,3}	{0,1,3}	yes	110
{0,1,2,3}	{0,2,3}	{0,1,2,3}	yes	111

The exponential blow-up. An NFA with n states can produce up to 2ⁿ DFA states, and sometimes all of them are needed. For "the n-th symbol from the end is 1", the NFA has n + 1 states, but every DFA needs at least 2ⁿ. Take two different strings of length n. They differ at some position i. Append i − 1 arbitrary symbols, so that position i becomes the n-th from the end: one extended string is accepted and the other is not. So the 2ⁿ strings of length n must lead to 2ⁿ different states.

def subset_construction(f, start, accept, alphabet):
    """NFA (no λ-moves) → equivalent DFA whose states are frozensets of NFA states."""
    start_set = frozenset([start])
    dfa, seen, todo = {}, {start_set}, [start_set]
    while todo:                                        # explore only reachable subsets
        T = todo.pop()
        for a in alphabet:
            U = frozenset(t for s in T for t in f.get((s, a), ()))
            dfa[T, a] = U
            if U not in seen:
                seen.add(U)
                todo.append(U)
    return dfa, start_set, {T for T in seen if T & accept}

def nth_from_last(n):
    """NFA with states 0..n accepting the strings whose n-th symbol from the end is 1."""
    f = {(0, "0"): {0}, (0, "1"): {0, 1}}              # state 0 waits, and on a 1 may guess
    for i in range(1, n):
        f[i, "0"] = f[i, "1"] = {i + 1}                # count the remaining symbols
    return f, 0, {n}

dfa, start, accepting = subset_construction(*nth_from_last(3), alphabet="01")
name = lambda T: "{" + ",".join(map(str, sorted(T))) + "}"
for T in sorted({T for T, _ in dfa}, key=lambda T: (len(T), sorted(T))):
    print(f"{name(T):10} 0→{name(dfa[T, '0']):10} 1→{name(dfa[T, '1']):10} {'accept' if T in accepting else ''}")
# {0}        0→{0}        1→{0,1}
# {0,1}      0→{0,2}      1→{0,1,2}
# {0,2}      0→{0,3}      1→{0,1,3}
# {0,3}      0→{0}        1→{0,1}      accept
# {0,1,2}    0→{0,2,3}    1→{0,1,2,3}
# {0,1,3}    0→{0,2}      1→{0,1,2}    accept
# {0,2,3}    0→{0,3}      1→{0,1,3}    accept
# {0,1,2,3}  0→{0,2,3}    1→{0,1,2,3}  accept

for n in range(1, 11):
    dfa, _, _ = subset_construction(*nth_from_last(n), alphabet="01")
    print(n + 1, "NFA states →", len({T for T, _ in dfa}), "DFA states")
# 2 NFA states → 2 DFA states
# 3 NFA states → 4 DFA states
# ...
# 11 NFA states → 1024 DFA states

In practice. Lexer generators such as flex convert the NFA for all token patterns into one DFA ahead of time, because the patterns are fixed and speed matters. RE2 and grep build DFA states lazily: a subset is created the first time the input reaches it and is kept in a bounded cache. This combines DFA speed on typical input with NFA-sized memory in the worst case.

Analogy. The subset construction replaces the crowd exploring the maze with one person carrying a clipboard. On the clipboard is the list of squares where the crowd currently stands. Each input symbol updates the whole list at once. There are only finitely many possible lists, so the clipboard-holder is a DFA.

Key takeaways

• The subset construction makes each DFA state a set of NFA states, starting from {s₀} or its λ-closure.
• A subset is accepting if it contains an NFA accepting state. The empty subset is the dead state.
• NFAs and DFAs recognize exactly the same languages.
• The construction can need 2ⁿ states, and for "n-th symbol from the end" every DFA does.
• Build only the reachable subsets, either eagerly (lexer generators) or lazily on demand (RE2, grep).

Practice

1. (Beginner) Draw an NFA with 3 states for the binary strings that end in 01, and convert it into a DFA with the subset construction. How many reachable subsets are there?
2. (Intermediate) Write out the lower-bound argument for "the n-th symbol from the end is 1" in full: show that any two distinct strings of length n must lead a DFA for this language to different states. Then show that the subset construction applied to the NFA reaches all 2ⁿ subsets that contain 0.
3. (Interview) A log-scanning service must check every line against several thousand patterns at line rate. Simulating the combined NFA is too slow, and the fully determinized DFA does not fit in memory. What would you do? Hint: consider building DFA states lazily with a bounded cache that is flushed when full (RE2's approach), splitting the patterns into groups, and, for plain literal strings, the Aho–Corasick automaton.

DFA Minimization

Why. Many DFAs recognize the same language, and the subset construction often produces redundant states. A smaller DFA uses smaller tables and less hardware, but the deeper benefit is a canonical form. For every regular language there is exactly one minimal DFA, up to renaming of states. So two automata or regular expressions describe the same language exactly when their minimal DFAs are the same. That turns "are these two patterns equivalent?" into a mechanical check.

What. First remove the states that are unreachable from the start (a graph search, 8.4). Two states p and q are equivalent, written p ≡ q, if no input string can tell them apart:

  p ≡ q   ⇔   for every w ∈ I*:  f*(p, w) ∈ F  ⇔  f*(q, w) ∈ F

This is an equivalence relation (2.5). Merging each equivalence class into one state gives the minimal DFA. A string w with f*(p, w) ∈ F but f*(q, w) ∉ F (or the other way round) is a distinguishing string for p and q.

Moore's algorithm (partition refinement). Call p and q k-equivalent if no string of length at most k distinguishes them.

1. Round 0: split the states into two blocks, accepting and non-accepting. Here λ already distinguishes the two blocks.
2. Round k + 1: two states stay in the same block if they were in the same block in round k and, for every symbol a, their a-successors were in the same block in round k.
3. Stop when a round splits nothing. The blocks are then the equivalence classes.

Each round that changes anything adds at least one block, so the algorithm stops after at most |S| rounds. The total time is O(|S|² · |I|). Hopcroft's algorithm does the same in O(|S| · |I| · log |S|).

Worked example. The DFA that tracks a binary number mod 6 and accepts remainders 0 and 3 recognizes the multiples of 3, but it has 6 states. The transition is r → (2r + b) mod 6.

  Round 0:  {0, 3}  {1, 2, 4, 5}                       accepting vs non-accepting

            successors (on 0, on 1) as blocks:  1 → (B, A)   2 → (B, B)   4 → (B, A)   5 → (B, B)
                                                with A = {0, 3}, B = {1, 2, 4, 5}
  Round 1:  {0, 3}  {1, 4}  {2, 5}                     B splits

  Round 2:  {0, 3}  {1, 4}  {2, 5}                     nothing splits: done

The three blocks are the remainders mod 3. The minimal DFA is exactly the 3-state automaton from earlier in this subchapter.

The Myhill–Nerode theorem. For a language L over I, call two strings x and y indistinguishable if xz ∈ L ⇔ yz ∈ L for every z. This is an equivalence relation on strings. The theorem says:

• L is regular if and only if this relation has finitely many classes;
• the number of classes equals the number of states of the minimal DFA for L.

This gives a non-regularity test too. For L = {aⁿbⁿ}, the strings a, aa, aaa, … are pairwise distinguishable (aⁱbⁱ ∈ L but aʲbⁱ ∉ L for j ≠ i). There are infinitely many classes, so no DFA recognizes L.

def minimize(states, alphabet, f, accept, verbose=False):
    """Moore's partition refinement. Returns the blocks of equivalent states.
    Assumes unreachable states have already been removed."""
    block = {s: int(s in accept) for s in states}            # round 0
    while True:
        if verbose:
            print(blocks(block))
        # A state's signature: its own block and the blocks of its successors
        sig = {s: (block[s],) + tuple(block[f[s, a]] for a in alphabet) for s in states}
        ids = {}
        refined = {s: ids.setdefault(sig[s], len(ids)) for s in states}
        if len(ids) == len(set(block.values())):              # no block split: stable
            return blocks(block)
        block = refined

def blocks(block):
    groups = {}
    for s, b in block.items():
        groups.setdefault(b, []).append(s)
    return sorted(sorted(g) for g in groups.values())

# Binary numbers mod 6, accepting remainders 0 and 3: the multiples of 3, with 6 states
f6 = {(r, b): (2 * r + int(b)) % 6 for r in range(6) for b in "01"}
print(minimize(range(6), "01", f6, accept={0, 3}, verbose=True))
# [[0, 3], [1, 2, 4, 5]]
# [[0, 3], [1, 4], [2, 5]]
# [[0, 3], [1, 4], [2, 5]]       3 blocks: the minimal DFA has 3 states

# Multiples of 6 (accept only remainder 0): 1 ≡ 4 and 2 ≡ 5, because both states of each
# pair are non-accepting and move to the same state on every symbol (2·4 ≡ 2·1 mod 6)
print(minimize(range(6), "01", f6, accept={0}))               # [[0], [1, 4], [2, 5], [3]]

Testing equivalence. To decide whether two DFAs recognize the same language, minimize both and check whether the results are isomorphic (8.2). Because DFAs are deterministic, the isomorphism check is a single simultaneous breadth-first search from the two start states. Alternatively, search the product automaton for a distinguishing string (Closure Properties, 13.3), which also gives a counterexample.

Analogy. Minimization is like merging duplicate support macros in a help desk. Two canned replies are duplicates if, whatever the customer says next, they lead to the same outcome. You start by separating "resolved" from "unresolved", then keep splitting groups whose members react differently to some message, until every group is consistent.

Key takeaways

• States are equivalent if no string distinguishes them. Merging equivalence classes gives the minimal DFA.
• Moore's algorithm starts from {accepting, non-accepting} and splits blocks until successors agree.
• The minimal DFA is unique up to renaming, so it is a canonical form, and it decides equivalence of regular languages.
• Myhill–Nerode: L is regular exactly when it has finitely many indistinguishability classes. Their number is the size of the minimal DFA.
• Infinitely many pairwise distinguishable prefixes prove that a language is not regular.

Practice

1. (Beginner) Build the DFA that tracks a binary number mod 4 and accepts remainders 0 and 2. Minimize it by hand. What language is it, and how many states remain?
2. (Intermediate) Use Myhill–Nerode to show that the minimal DFA for "the third symbol from the end is 1" has exactly 8 states, and that {w ∈ {(, )}* : w is balanced} is not regular.
3. (Interview) Two engineers wrote different regular expressions for valid product codes, and you need to know whether they accept exactly the same strings. If they do not, you want the shortest string on which they disagree. How do you do it? Hint: compile both into DFAs. Then either minimize both and compare them, or search the product automaton breadth-first for a state that is accepting in exactly one component. BFS (8.4) gives the shortest counterexample.

<a id="133-regular-languages"></a>

13.3 Regular Languages

This subchapter shows that three very different descriptions (regular expressions, finite automata and regular grammars) define the same family of languages. It then studies which operations keep a language in that family, and gives a tool for proving that a language is outside it.

Regular Expressions

Why. Automata are machines: precise, but long to write down and hard to read in text. Searching a log file needs a compact one-line notation for patterns such as "a date", "an email-like token" or "a line ending in an error code". Regular expressions are that notation. They build patterns from single symbols with three operations, and they are used in grep, in editors, in lexer generators, in input validation and in almost every programming language's standard library.

What. Regular expressions over an alphabet I are defined recursively (3.3):

Expression	Language it denotes
∅	∅, the empty language
λ	{λ}
x, for each x ∈ I	{x}
(AB), for regular expressions A, B	L(A)L(B), concatenation
(A ∪ B)	L(A) ∪ L(B), union (also written A + B or A | B)
A*	L(A)*, Kleene star

The regular sets (regular languages) are the languages denoted by regular expressions. To save parentheses, star binds tightest, then concatenation, then union, so ab* ∪ c means (a(b*)) ∪ c.

Regular expression over {0, 1}	Language
(0 ∪ 1)*	All strings
(0 ∪ 1)*1	Strings ending in 1: the odd binary numbers
0*10*	Strings with exactly one 1
(0 ∪ 1)*00(0 ∪ 1)*	Strings containing 00
(1 ∪ 01)*(λ ∪ 0)	Strings with no two consecutive 0s
((0 ∪ 1)(0 ∪ 1))*	Strings of even length
1*(01*01*)*	Strings with an even number of 0s

Reading a regular expression. Take (1 ∪ 01)*(λ ∪ 0). The starred part glues together blocks 1 and 01, so every 0 inside it is immediately followed by a 1. The optional final 0 allows one trailing 0. A string has no 00 exactly when it can be cut this way.

Algebraic laws. Regular expressions satisfy identities that are used to simplify them, much like the laws of Boolean algebra (11.1):

Law	Identity
Union is associative, commutative and idempotent	A ∪ (B ∪ C) = (A ∪ B) ∪ C, A ∪ B = B ∪ A, A ∪ A = A
Identities	A ∪ ∅ = A, Aλ = λA = A
Annihilator	A∅ = ∅A = ∅
Distributivity	A(B ∪ C) = AB ∪ AC, (A ∪ B)C = AC ∪ BC
Star	(A*)* = A*, ∅* = λ, A* = λ ∪ AA*
Shifting	A(BA)* = (AB)*A
Union under star	(A ∪ B)* = (A*B*)*

Concatenation is not commutative, and (A ∪ B)* is not A* ∪ B*: ab is in the first but not in the second.

Practical regex syntax. Programming languages add many shorthands. Most are still regular, because each translates into the three basic operations. A few are not:

Syntax	Meaning	In basic operations	Regular?
a|b, ab, a*	Union, concatenation, star	The definition	Yes
a+, a?	One or more, optional	aa*, a ∪ λ	Yes
[a-z], .	Character class, any character	A union of symbols	Yes
a{2,4}	Bounded repetition	aa ∪ aaa ∪ aaaa	Yes
^, $, fullmatch	Anchors: match the whole string	Membership in the language	Yes
(a+)\1	Backreference: repeat the captured text	Denotes {ww}-like languages	No
(?R) (PCRE)	Recursion	Balanced nesting	No

Plain re.search finds a substring that matches, which is the same as matching .*R.* against the whole string. The theory talks about whole-string matching, which is re.fullmatch in Python.

import re
from itertools import product

def strings_of_length(n, alphabet="01"):
    return ("".join(t) for t in product(alphabet, repeat=n))

# (1 ∪ 01)*(λ ∪ 0): in Python, ∪ is | and λ is an empty alternative
no00 = re.compile(r"(1|01)*(|0)")
print(all((no00.fullmatch(w) is not None) == ("00" not in w)
          for n in range(13) for w in strings_of_length(n)))     # True: the regex is correct

# Counting the strings of each length with no 00: Fibonacci numbers again (6.1)
print([sum(1 for w in strings_of_length(n) if no00.fullmatch(w)) for n in range(10)])
# [1, 2, 3, 5, 8, 13, 21, 34, 55, 89]

# Even number of 0s
even0 = re.compile(r"1*(01*01*)*")
print(all((even0.fullmatch(w) is not None) == (w.count("0") % 2 == 0)
          for n in range(13) for w in strings_of_length(n)))     # True

# A backreference recognizes {ww}, which is not regular (see the pumping lemma)
square = re.compile(r"(.*)\1")
print([bool(square.fullmatch(w)) for w in ["abab", "abba", "", "aaaa", "aab"]])
# [True, False, True, True, False]

Analogy. A regular expression is a recipe written with three verbs: "then" (concatenation), "or" (union) and "repeat any number of times" (star). Anything you can say with those three verbs, starting from single letters, is a regular expression.

Key takeaways

• Regular expressions are built from ∅, λ and single symbols with concatenation, union and star. The regular sets are the languages they denote.
• Precedence: star, then concatenation, then union.
• Algebraic laws such as A(BA)* = (AB)*A and (A ∪ B)* = (A*B*)* simplify expressions. Concatenation is not commutative.
• Practical shorthands such as +, ?, classes and bounded repeats are still regular. Backreferences and recursion are not.
• The theory matches the whole string, which is fullmatch in Python, or ^…$ with search.

Practice

1. (Beginner) Write regular expressions over {0, 1} for: (a) strings with an odd number of 1s; (b) strings where every 0 is immediately followed by 11; (c) strings of length at most 3. Test each one with re.fullmatch against a brute-force check.
2. (Intermediate) Prove or disprove each identity: (a) (A ∪ B)* = A* ∪ B*; (b) (AB)*A = A(BA)*; (c) (A*B)*A* = (A ∪ B)*; (d) A*A* = A*. Hint: for a "prove", show that every string of each side belongs to the other. For a "disprove", one string over {a, b} is enough.
3. (Interview) A web service validates user input with the regex ^(a+)+$. A request containing 40 as followed by ! takes minutes and pins a CPU. Explain why, and name three ways to fix it. Hint: a backtracking engine tries every way of splitting the as between the inner and outer + before it gives up, and there are about 2ⁿ of them. Fixes: simplify the pattern (it equals ^a+$), use atomic groups or possessive quantifiers, set a timeout, or use a linear-time engine (RE2, Rust regex) that simulates the automaton.

Kleene's Theorem

Why. We now have three ways to describe a set of strings: regular expressions, which are compact and good for humans; finite automata, which are fast and good for machines; and regular grammars (13.1), which generate strings. It would be inconvenient if they described different families. Kleene's theorem (1956) says they do not, and its proof is the algorithm that every regex engine starts from: compile the expression into an automaton.

What.

Kleene's theorem. A language is regular (denoted by a regular expression) if and only if it is recognized by a finite automaton.

Together with the grammar correspondence below, these are all equivalent for a language L:

  L = L(R) for a regular expression R
      ⇕   Thompson's construction (⇓) and state elimination (⇑)
  L = L(N) for an NFA N
      ⇕   subset construction (13.2) and "a DFA is an NFA"
  L = L(D) for a DFA D
      ⇕   states ↔ nonterminals, transitions ↔ productions
  L = L(G) for a regular (type 3) grammar G

Regular expression ⇒ NFA (Thompson's construction). Build an NFA with one start state and one accepting state, by structural induction (3.3) on the expression:

  ∅:         (s)          (t)                    no edge at all

  λ:         (s) ──λ──▶ (t)

  symbol x:  (s) ──x──▶ (t)

  A ∪ B:               ┌──λ──▶ [ A ] ──λ──┐
                (s) ───┤                  ├───▶ (t)
                       └──λ──▶ [ B ] ──λ──┘

  AB:        [ A ] ──λ──▶ [ B ]               A's accepting state links to B's start

  A*:                        ┌──── λ ─────┐
                             ▼            │
                (s) ──λ──▶ [ A ] ─────────┴──λ──▶ (t)
                 │                                 ▲
                 └────────────────λ────────────────┘

In the star fragment, the upper λ edge goes from the end of A back to its start (repeat), and the lower one skips A entirely (zero repetitions). Each operator adds at most two states, so an expression of length m gives an NFA with O(m) states and edges. Simulating it with sets of states (13.2) matches a string of length n in O(mn) time, with no exponential backtracking.

NFA ⇒ regular expression (state elimination). Allow edges labeled with regular expressions instead of single symbols. Add a new start state and a new accepting state, connected by λ edges. Then remove the original states one at a time. When a state q is removed, every path p → q → r is replaced by a direct edge:

  R(p, r)  :=  R(p, r)  ∪  R(p, q) R(q, q)* R(q, r)

R(q, q) is the self-loop on q (∅ if there is none, and ∅* = λ). When only the new start and accepting states are left, the label of the edge between them is the regular expression.

Example. A DFA for "an even number of 0s" has states E (start, accepting) and O, with E →⁰ O, O →⁰ E, and self-loops on 1 at both. Removing O turns the path E →⁰ O →¹* O →⁰ E into a new self-loop 01*0 on E. Together with the existing loop 1, the result is (1 ∪ 01*0)*. This is a different, equally correct expression from the 1*(01*01*)* of the previous topic.

Finite automata ⇔ regular grammars. For a DFA, make one nonterminal per state (the start state becomes S). Each transition f(A, a) = B becomes the production A → aB, and each accepting state A gets A → λ. Then a derivation S ⇒ a₁A₁ ⇒ a₁a₂A₂ ⇒ ⋯ follows a run of the automaton step by step. Productions of the form A → λ for states other than the start can be removed again, giving the strict type 3 form of 13.1. Read in the other direction, the same correspondence turns a regular grammar into an NFA.

import re
from itertools import count, product

def thompson(pattern):
    """Compile a regex with single-character symbols, |, *, ( ) into an NFA with λ-edges.
    Grammar (13.1):  alt ::= cat ("|" cat)*   cat ::= star*   star ::= atom "*"*   atom ::= x | "(" alt ")"
    Each parse function returns a fragment (start, accept)."""
    new_state, edges, pos = count(), [], 0           # edges are (from, symbol or None for λ, to)

    def peek():
        return pattern[pos] if pos < len(pattern) else None

    def alt():
        nonlocal pos
        s, t = cat()
        while peek() == "|":
            pos += 1
            s2, t2 = cat()
            s0, t0 = next(new_state), next(new_state)                  # union fragment
            edges.extend([(s0, None, s), (s0, None, s2), (t, None, t0), (t2, None, t0)])
            s, t = s0, t0
        return s, t

    def cat():
        s = t = next(new_state)                      # an empty concatenation matches λ
        while peek() not in (None, "|", ")"):
            s2, t2 = star()
            edges.append((t, None, s2))              # link the fragments with a λ-edge
            t = t2
        return s, t

    def star():
        nonlocal pos
        s, t = atom()
        while peek() == "*":
            pos += 1
            s0, t0 = next(new_state), next(new_state)                  # star fragment
            edges.extend([(s0, None, s), (t, None, s), (t, None, t0), (s0, None, t0)])
            s, t = s0, t0
        return s, t

    def atom():
        nonlocal pos
        ch = peek()
        pos += 1
        if ch == "(":
            s, t = alt()
            pos += 1                                 # skip the closing ")"
            return s, t
        s, t = next(new_state), next(new_state)
        edges.append((s, ch, t))
        return s, t

    start, accept = alt()
    return start, accept, edges

def nfa_match(nfa, w):
    start, accept, edges = nfa
    def closure(states):
        stack, result = list(states), set(states)
        while stack:
            q = stack.pop()
            for a, sym, b in edges:
                if a == q and sym is None and b not in result:
                    result.add(b)
                    stack.append(b)
        return result
    current = closure({start})
    for ch in w:
        current = closure({b for a, sym, b in edges if a in current and sym == ch})
    return accept in current

for pattern, alphabet in [("(1|01)*(|0)", "01"), ("(a|b)*abb", "ab"), ("(1|01*0)*", "01")]:
    nfa = thompson(pattern)
    agrees = all(nfa_match(nfa, w) == bool(re.fullmatch(pattern, w))     # Python's re as the oracle
                 for n in range(10) for w in map("".join, product(alphabet, repeat=n)))
    print(f"{pattern:12} {len({q for e in nfa[2] for q in (e[0], e[2])}):2} states  agrees with re: {agrees}")
# (1|01)*(|0)  19 states  agrees with re: True
# (a|b)*abb    17 states  agrees with re: True
# (1|01*0)*    17 states  agrees with re: True

The NFAs are much larger than necessary: the last pattern denotes "an even number of 0s", whose minimal DFA has 2 states. Real compilers follow Thompson's construction with λ-removal, the subset construction and minimization (13.2).

Analogy. Thompson's construction is Lego. There is one brick for each symbol and one connector for each of "or", "then" and "repeat", and every connector has one plug in and one plug out. Any expression snaps together into a machine, and the machine has as many parts as the expression has symbols.

Key takeaways

• Kleene's theorem: regular expressions and finite automata describe exactly the same languages. So do regular grammars.
• Thompson's construction compiles a regular expression into an NFA with O(m) states, one small fragment per operator, glued with λ-edges.
• State elimination turns an automaton into a regular expression by removing states and rerouting paths through R(p,q) R(q,q)* R(q,r).
• DFA states correspond to grammar nonterminals, and transitions to productions A → aB.
• The standard pipeline is regex → NFA → DFA → minimal DFA.

Practice

1. (Beginner) Apply Thompson's construction by hand to (a ∪ b)*abb and count the states. Then write a regular grammar for the "even number of 0s" DFA and derive 0110.
2. (Intermediate) Use state elimination on the 3-state DFA for binary multiples of 3 (13.2) to obtain a regular expression. Hint: eliminate state 2 first. It creates a self-loop 01*0 on state 1. Check your answer against (0 ∪ 1(01*0)*1)* with the brute-force tester from this topic.
3. (Interview) Implement a matcher for patterns with literal characters, . (any character) and * (zero or more of the preceding element) that always runs in O(|pattern| · |text|) time. Hint: either simulate the Thompson NFA with sets of states, or fill a table match[i][j] meaning "text[i:] matches pattern[j:]". The two approaches visit the same (position, state) pairs.

Closure Properties

Why. Specifications are often combinations: "a valid identifier that is not a keyword", "a log line that matches rule A and rule B", "any string except these". If the regular languages are closed under an operation, the combination is again regular and a DFA can recognize it. Closure properties also work backwards. If an operation would turn a language into one that is known to be non-regular, the original language could not have been regular either.

What. A family of languages is closed under an operation if applying the operation to members of the family always gives a member. The regular languages are closed under all the usual operations:

Operation	Construction	DFA size
Union L₁ ∪ L₂	Regular expression R₁ ∪ R₂, or the product automaton	≤ n₁n₂
Concatenation L₁L₂	Regular expression R₁R₂	Can be exponential
Star L*	Regular expression R*	Can be exponential
Complement I* − L	Swap accepting and non-accepting states of a complete DFA	n
Intersection L₁ ∩ L₂	Product automaton, or De Morgan: complement of L̄₁ ∪ L̄₂	≤ n₁n₂
Difference L₁ − L₂	L₁ ∩ L̄₂	≤ n₁n₂
Reversal Lᴿ	Reverse every edge, swap start and accepting states (gives an NFA)	Can be exponential
Homomorphic image h(L)	Replace each symbol a in the expression by the string h(a)	—

The product construction. Run two DFAs M₁ = (S₁, I, f₁, s₁, F₁) and M₂ = (S₂, I, f₂, s₂, F₂) side by side on the same input. The pair of their states is the state of a single DFA:

  states:      S₁ × S₂                       (Cartesian product, 2.1)
  start:       (s₁, s₂)
  transition:  f((p, q), a) = (f₁(p, a), f₂(q, a))
  accepting:   F₁ × F₂                       for L₁ ∩ L₂
               (F₁ × S₂) ∪ (S₁ × F₂)         for L₁ ∪ L₂
               F₁ × (S₂ − F₂)                for L₁ − L₂
               pairs with exactly one in F   for L₁ Δ L₂, the symmetric difference

Pitfall: complementing an NFA. Swapping the accepting states only works for a complete DFA. Every string must reach exactly one state, and missing transitions must first be routed to an explicit dead state. For an NFA, "some path accepts" is not the opposite of "some path rejects". The NFA with states p (accepting) and q, where p goes to both p and q on a, recognizes a*. With the states swapped, it accepts a⁺, but the complement of a* over {a} is ∅.

Decision procedures. Because DFAs are finite graphs, the basic questions about regular languages can be answered by graph search (8.4):

Question	Algorithm
Is L(M) empty?	Is any accepting state reachable from the start? (BFS)
Is L(M) infinite?	Is there a cycle on some path from the start to an accepting state?
Is L₁ ⊆ L₂?	Is L₁ − L₂ empty? (product automaton)
Is L₁ = L₂?	Is L₁ Δ L₂ empty? Or compare minimal DFAs (13.2)

BFS on the product automaton also returns the shortest string in the difference, which is a concrete counterexample.

from collections import deque

def mod_dfa(k, accept):
    """DFA over {0, 1}: the state is the value of the binary prefix mod k."""
    return {"start": 0, "accept": set(accept),
            "f": {(r, b): (2 * r + int(b)) % k for r in range(k) for b in "01"}}

def product(A, B, combine, alphabet="01"):
    """Product DFA. combine(in_A, in_B) decides acceptance: and, or, and-not, xor, ..."""
    start = (A["start"], B["start"])
    f, accept, seen, queue = {}, set(), {start}, deque([start])
    while queue:
        p, q = state = queue.popleft()
        if combine(p in A["accept"], q in B["accept"]):
            accept.add(state)
        for a in alphabet:
            nxt = f[state, a] = (A["f"][p, a], B["f"][q, a])
            if nxt not in seen:
                seen.add(nxt)
                queue.append(nxt)
    return {"start": start, "accept": accept, "f": f, "size": len(seen)}

def shortest_word(D, alphabet="01"):
    """BFS for a shortest accepted string. None means that L(D) is empty."""
    queue, seen = deque([(D["start"], "")]), {D["start"]}
    while queue:
        state, w = queue.popleft()
        if state in D["accept"]:
            return w
        for a in alphabet:
            nxt = D["f"][state, a]
            if nxt not in seen:
                seen.add(nxt)
                queue.append((nxt, w + a))
    return None

mult3 = mod_dfa(3, [0])               # multiples of 3, 3 states
mult3_via6 = mod_dfa(6, [0, 3])       # also multiples of 3, but with 6 states
mult6 = mod_dfa(6, [0])               # multiples of 6

xor = lambda x, y: x != y
and_not = lambda x, y: x and not y
print(shortest_word(product(mult3, mult3_via6, xor)))      # None: the symmetric difference is empty, same language
print(shortest_word(product(mult3, mult6, and_not)))       # 11: three is a multiple of 3 but not of 6
print(shortest_word(product(mult6, mult3, and_not)))       # None: every multiple of 6 is a multiple of 3
print(product(mult3, mod_dfa(5, [0]), lambda x, y: x and y)["size"])   # 15 reachable pairs: multiples of 15

Proving non-regularity with closure. Let L = {w ∈ {a, b}* : w has equally many a's and b's}. If L were regular, then L ∩ a*b* = {aⁿbⁿ} would be regular too, as the intersection of two regular languages. It is not (13.2, Myhill–Nerode, and the pumping lemma below), so L is not regular either. The argument needed no new pumping, only one known non-regular language and one closure property.

What is not preserved. A subset of a regular language need not be regular: {aⁿbⁿ} ⊆ a*b*. Neither is an infinite union of regular languages, since every language is the union of its singletons. Closure holds for finitely many applications of the operations.

Analogy. The product construction is two referees watching the same match, each keeping their own scorecard. Afterwards the decision combines their verdicts: both say yes (intersection), either says yes (union), or they disagree (symmetric difference).

Key takeaways

• Regular languages are closed under union, concatenation, star, complement, intersection, difference, reversal and homomorphisms.
• The product automaton runs two DFAs in lockstep. Its accepting set chooses the Boolean combination.
• Complement by swapping accepting states requires a complete DFA, not an NFA.
• Emptiness, finiteness, inclusion and equivalence of regular languages are decidable by graph search. BFS also produces a shortest counterexample.
• To prove non-regularity, combine the language with regular ones until a known non-regular language appears.

Practice

1. (Beginner) Draw DFAs for "an even number of as" and "ends in b" over {a, b}, then draw their product automaton for the intersection. How many states does it have, and which are accepting?
2. (Intermediate) Prove that {w ∈ {a, b}* : #a(w) ≠ #b(w)} and {aⁿbᵐ : n ≠ m} are not regular, using closure properties and the fact that {aⁿbⁿ} is not regular. Then show that if L is regular, so is half(L) = {x : xy ∈ L for some y with |y| = |x|}. Hint: for the first two, use the complement and an intersection with a*b*.
3. (Interview) A firewall has a block list and an allow list of URL patterns, both written as regular expressions. Before deploying a change, you want to report every pattern pair that conflicts, with an example URL that both match. How would you implement this, and what could make it slow? Hint: for each pair, build the product of the two DFAs and BFS for an accepting pair state, which gives a shortest witness URL. The product has up to n₁n₂ states, and determinizing patterns like .*a.{20} blows up exponentially.

Pumping Lemma for Regular Languages

Why. To prove that a language is regular, you show an automaton or a regular expression. To prove that it is not, you must show that no finite automaton recognizes it, and there are infinitely many automata to rule out. The pumping lemma gives a property that every regular language has. A language without the property is therefore not regular. The key idea is the pigeonhole principle (5.4): a DFA with p states that reads p symbols visits p + 1 states, so some state repeats, and the part of the input read between the two visits is a loop that can be repeated or skipped.

What.

Pumping lemma. If L is regular, there is a number p ≥ 1 (the pumping length) such that every w ∈ L with |w| ≥ p can be written as w = xyz where:

1. |xy| ≤ p,
2. |y| ≥ 1,
3. xyⁱz ∈ L for every i ≥ 0.

Proof. Let M be a DFA for L with p states, and let w ∈ L with |w| ≥ p. While M reads the first p symbols of w, it is in p + 1 states r₀, r₁, …, rₚ (counting the start state). By the pigeonhole principle, rⱼ = rₖ for some j < k ≤ p. Let x be the first j symbols, y the symbols j + 1, …, k, and z the rest. Reading y takes M from the state q = rⱼ back to q, so the loop can be taken any number of times (i = 0, 1, 2, …) without changing where z leads, and z leads to an accepting state.

                       ┌──── y ────┐
                       ▼           │
  ──▶ ( s₀ ) ── x ──▶ ( q ) ───────┘
                       │
                       └──── z ────▶ (( f ))

Using the lemma. It is used in its contrapositive form, as a game against an adversary. The quantifiers in the lemma, ∃p ∀w ∃xyz ∀i, are negated as in 1.2:

Turn	Who	Move
1	Adversary	Picks the pumping length p
2	You	Pick a string w ∈ L with |w| ≥ p (it may depend on p)
3	Adversary	Splits w = xyz with |xy| ≤ p and |y| ≥ 1
4	You	Pick an i ≥ 0 with xyⁱz ∉ L

If you can win for every p and every split, L is not regular. The condition |xy| ≤ p is your main weapon: choose w so that its first p symbols are all the same, and y is forced to consist of that symbol.

Example 1: L = {aⁿbⁿ : n ≥ 0}. Choose w = aᵖbᵖ. Because |xy| ≤ p, both x and y lie inside the as, so y = aᵏ with k ≥ 1. Pump up with i = 2: xy²z = aᵖ⁺ᵏbᵖ has more as than bs, so it is not in L. Hence L is not regular. This is why no regular expression can match balanced parentheses: replace a with ( and b with ).

Example 2: palindromes over {a, b}. Choose w = aᵖbaᵖ. Again y = aᵏ lies in the first block. Pumping down (i = 0) gives aᵖ⁻ᵏbaᵖ, which is not a palindrome.

Example 3: L = {aⁿ : n is prime}. Choose a prime q ≥ p + 2 and w = a^q. The adversary picks y = aᵏ with 1 ≤ k ≤ p. Take i = q − k. The length of xyⁱz is (q − k) + ik = (q − k)(k + 1). Both factors are at least 2, since q − k ≥ 2 and k + 1 ≥ 2, so the length is not prime.

Pitfalls.

• The lemma is a necessary condition, not a sufficient one. Some non-regular languages can be pumped, so pumping successfully proves nothing. Myhill–Nerode (13.2) is an exact characterization.
• You do not choose p or the split. An argument that handles only the split you would like ("let y = ab") is incomplete.
• A badly chosen w can make the proof impossible. For palindromes, w = aᵖ stays a palindrome however it is pumped. w = aᵖbaᵖ works because the b marks the centre and y cannot reach it.

import re

def pumpable(w, p, in_L, i_values=range(4)):
    """Look for a split w = xyz with |xy| <= p and |y| >= 1 that stays in L for every tested i."""
    for xy_len in range(1, p + 1):
        for x_len in range(xy_len):
            x, y, z = w[:x_len], w[x_len:xy_len], w[xy_len:]
            if all(in_L(x + y * i + z) for i in i_values):
                return x, y, z
    return None

# A regular language: no two consecutive 0s. Its DFA has 3 states (with the dead state), so p = 3
no00 = lambda s: "00" not in s
print(pumpable("1011011", 3, no00))      # ('', '1', '011011'): pumping the first 1 is harmless

# aⁿbⁿ: for every p, no split of aᵖbᵖ survives pumping
anbn = lambda s: re.fullmatch(r"a*b*", s) is not None and s.count("a") == s.count("b")
print(all(pumpable("a" * p + "b" * p, p, anbn) is None for p in range(1, 30)))     # True

# The choice of w matters. For palindromes, w = aᵖ survives pumping; w = aᵖbaᵖ does not
palindrome = lambda s: s == s[::-1]
print(pumpable("a" * 5, 5, palindrome))                   # ('', 'a', 'aaaa'): this w proves nothing
print(pumpable("a" * 5 + "b" + "a" * 5, 5, palindrome))   # None

Analogy. A finite automaton is a hiker with a map of p landmarks. On any trail longer than p steps, the hiker passes some landmark twice. Between the two visits is a loop, and the hiker could have walked it zero times or ten times and still finished at the same place. A language whose members cannot survive such a detour is not a hiking trail of any finite map.

Key takeaways

• Every regular language has a pumping length p: long strings contain a short loop y near the start that can be repeated or deleted.
• The proof is the pigeonhole principle applied to the states visited while reading the first p symbols.
• Use the contrapositive as a game: you pick w, the adversary picks the split, you pick i. You must win against every split.
• Choose w so that the first p symbols are uniform. That forces the shape of y.
• The lemma only proves non-regularity. Pumping successfully proves nothing.

Practice

1. (Beginner) Use the pumping lemma to show that {0ⁿ1²ⁿ : n ≥ 0} and {ww : w ∈ {a, b}*} are not regular. Hint: for the second, choose w = aᵖbaᵖb.
2. (Intermediate) Show that {a^(n²) : n ≥ 0} is not regular. Hint: the gap between consecutive squares, (n + 1)² − n² = 2n + 1, grows without bound, but pumping once adds at most p symbols. Then find a non-regular language that nevertheless satisfies the conclusion of the pumping lemma. (Look up {aⁱbʲcᵏ : i = 0 or j = k}.)
3. (Interview) A colleague wants to validate that HTML fragments have properly nested tags with a single regular expression, and claims "it just needs to be clever enough". What do you tell them? Hint: nesting contains {(ⁿ)ⁿ}, so pump the opening tags. Then discuss what does work: a stack-based parser (13.4), or a real HTML parser. Note that PCRE's recursive patterns are not regular expressions in the sense of this chapter.

<a id="134-computability"></a>

13.4 Computability

This subchapter gives finite automata more memory: first a stack, then an unbounded tape. That leads to a model that is believed to capture every algorithm, and then to a proof that some precisely stated problems cannot be solved by any algorithm at all.

Pushdown Automata

Why. Finite automata cannot count without bound, so they cannot check aⁿbⁿ, balanced parentheses, or begin … end blocks nested to any depth (13.3). Yet compilers check nesting all the time, with a stack: push on every opening symbol, pop on every closing one. A finite automaton with a stack attached is called a pushdown automaton. It recognizes exactly the context-free languages, the type 2 grammars of 13.1, which makes it the machine behind every parser.

What. A pushdown automaton (PDA) is M = (Q, Σ, Γ, δ, q₀, Z₀, F):

• Q is a finite set of states, q₀ the start state, and F ⊆ Q the accepting states;
• Σ is the input alphabet and Γ the stack alphabet, with a bottom marker Z₀ ∈ Γ that is on the stack at the start;
• δ maps (state, input symbol or λ, top of stack) to a finite set of moves (new state, string to push).

A move labeled a, X → γ means: read a (or nothing, if a = λ), pop the top symbol X, and push the string γ (its first symbol becomes the new top). So X → λ pops, X → X leaves the stack alone, and X → YX pushes Y. The PDA accepts w if some sequence of moves reads all of w and ends in an accepting state. Acceptance by empty stack gives the same class of languages.

A configuration (instantaneous description) is a triple (state, remaining input, stack contents). A run is a sequence of configurations.

Example: {aⁿbⁿ : n ≥ 0}. Push an A for each a, pop one for each b, and accept when the bottom marker reappears exactly when the input ends:

  ──▶ ( q0 ) ──── b, A → λ ────▶ ( q1 ) ──── λ, Z → Z ────▶ (( q2 ))
        │                                                      ▲
        └──────────────────────── λ, Z → Z ────────────────────┘    (n = 0)

  self-loops:  q0 on  a, Z → AZ  and  a, A → AA        push one A per a
               q1 on  b, A → λ                         pop one A per b

Step	State	Remaining input	Stack (top first)
0	q0	aabb	Z
1	q0	abb	AZ
2	q0	bb	AAZ
3	q1	b	AZ
4	q1	λ	Z
5	q2	λ	Z: accept

On aab, the run gets stuck in q1 with AZ on the stack. On abb, it reaches Z with a b still unread. Both are rejected.

PDAs and grammars.

Theorem. A language is context-free if and only if some (nondeterministic) PDA accepts it.

From a grammar to a PDA: keep the unfinished part of a leftmost derivation on the stack. If the top is a nonterminal A, replace it by the right side of some production A → α (a nondeterministic λ-move). If the top is a terminal, match it against the next input symbol and pop it. This is exactly how a top-down (LL) parser works.

Determinism matters here. Unlike for finite automata (13.2), nondeterministic PDAs are strictly more powerful than deterministic ones. The even-length palindromes {wwᴿ} need a PDA that guesses where the middle is, and no deterministic PDA recognizes them. The deterministic context-free languages are exactly those that LR(1) parsers handle, and parser generators such as yacc and bison target them.

Property	Regular	Context-free
Machine	DFA = NFA	Nondeterministic PDA, strictly stronger than deterministic
Closed under union, concatenation, star	Yes	Yes
Closed under intersection, complement	Yes	No: {aⁿbⁿcᵐ} ∩ {aᵐbⁿcⁿ} = {aⁿbⁿcⁿ}
Intersection with a regular language	Regular	Context-free
Membership	O(n)	O(n³) in general (CYK), O(n) for LL/LR grammars
Emptiness	Decidable	Decidable
Equivalence	Decidable	Undecidable
Pumping lemma	xyⁱz	uvⁱxyⁱz: two pumps in step

The pumping lemma for context-free languages shows that {aⁿbⁿcⁿ} is not context-free: one stack can match the as against the bs, but then that count is gone when the cs arrive. Two stacks are enough, but a PDA with two stacks is as powerful as a Turing machine (next topic).

def pda_accepts(delta, w, start="q0", bottom="Z", accept=("q2",)):
    """Nondeterministic PDA: depth-first search over configurations (state, input position, stack).
    delta maps (state, input symbol or "", top) to a list of (new state, string pushed for top)."""
    todo, seen = [(start, 0, bottom)], set()
    while todo:
        config = todo.pop()
        if config in seen:
            continue
        seen.add(config)
        state, i, stack = config                     # stack is a string with its top at index 0
        if i == len(w) and state in accept:
            return True
        if not stack:
            continue
        top, rest = stack[0], stack[1:]
        moves = [("", i)] + ([(w[i], i + 1)] if i < len(w) else [])   # λ-move, or read a symbol
        for symbol, j in moves:
            for new_state, push in delta.get((state, symbol, top), []):
                todo.append((new_state, j, push + rest))
    return False

# aⁿbⁿ, as in the diagram
anbn = {("q0", "a", "Z"): [("q0", "AZ")], ("q0", "a", "A"): [("q0", "AA")],
        ("q0", "b", "A"): [("q1", "")], ("q1", "b", "A"): [("q1", "")],
        ("q1", "", "Z"): [("q2", "Z")], ("q0", "", "Z"): [("q2", "Z")]}
print([pda_accepts(anbn, w) for w in ["", "ab", "aabb", "aab", "abb", "abab"]])
# [True, True, True, False, False, False]

# Even-length palindromes: push the first half, guess the middle (a λ-move), pop-match the second half
pal = {("q1", "", "Z"): [("q2", "Z")]}
for x in "ab":
    for top in "abZ":
        pal[("q0", x, top)] = [("q0", x + top)]      # first half: push every symbol
    pal[("q1", x, x)] = [("q1", "")]                 # second half: pop the matching symbol
for top in "abZ":
    pal[("q0", "", top)] = [("q1", top)]             # nondeterministic guess: "this is the middle"

from itertools import product
words = ["".join(t) for n in range(9) for t in product("ab", repeat=n)]
print(all(pda_accepts(pal, w) == (w == w[::-1] and len(w) % 2 == 0) for w in words))   # True

Analogy. A PDA is a cafeteria worker with a stack of trays. They can always see and take the top tray, and put new trays on top, but they cannot look further down without removing the trays above. That is enough to match every opening bracket with its closing bracket, but not to compare three counts.

Key takeaways

• A PDA is a finite automaton plus an unbounded stack. Each move reads a symbol or λ, pops the top and pushes a string.
• PDAs recognize exactly the context-free languages. A grammar becomes a PDA that expands nonterminals on the stack, which is how top-down parsing works.
• Nondeterminism adds power for PDAs: {wwᴿ} needs a guess. Deterministic CFLs are what LR parsers handle.
• Context-free languages are closed under union, concatenation and star, but not under intersection or complement.
• {aⁿbⁿcⁿ} is not context-free. A second stack gives full Turing-machine power.

Practice

1. (Beginner) Trace the aⁿbⁿ PDA on aabbb and on aaabb with a configuration table, and say exactly where each run fails.
2. (Intermediate) Design a PDA for {w ∈ {a, b}* : #a(w) = #b(w)} and test it with pda_accepts. Hint: keep the surplus on the stack. On a, pop a B if one is on top, otherwise push an A, and symmetrically for b.
3. (Interview) Write a function that checks whether a string with (), [] and {} is properly nested, in one pass. How much memory does it need in the worst case? If there were only one kind of bracket, how would the memory requirement change, and which machine model would that be? Hint: a stack of open brackets is a deterministic PDA. With one bracket type, a single counter suffices (O(log n) bits), which is a one-counter automaton. The counter must never go negative.

Turing Machines

Why. Finite automata and PDAs are too weak to model a general computer: {aⁿbⁿcⁿ} and multiplication are already beyond them. In 1936, before electronic computers existed, Alan Turing asked what a human clerk with pencil and paper can compute by following rules. His answer abstracts the clerk into a finite set of "states of mind", an unbounded supply of paper (the tape), and the ability to read, write and move one symbol at a time. This simple machine turns out to compute everything any known computer can compute, which makes it the standard model for asking what is computable at all.

What. A Turing machine T = (S, I, f, s₀) consists of:

• a finite set of states S with a start state s₀;
• a tape alphabet I that contains a blank symbol B;
• a partial transition function f: S × I → S × I × {L, R}.

The tape is infinite in both directions and divided into cells. All but finitely many cells hold B. A read/write head is over one cell at a time. If the machine is in state s reading x and f(s, x) = (s', x', d), it writes x', moves one cell in direction d, and enters state s'. If f(s, x) is undefined, the machine halts. It may also never halt.

A Turing machine is used in two ways:

• As a recognizer. Mark some states as final. T accepts w if, started on w, it halts in a final state. T rejects w if it halts in a non-final state. On some inputs it may run forever, which is neither.
• As a function. Encode the input on the tape and run T. If it halts, the tape contents are the output. A function that some TM computes this way is computable.

	Finite automaton	Pushdown automaton	Turing machine
Memory	States only	States + stack	States + unbounded tape
Access to memory	—	Top of the stack only	Any cell, by moving the head
Input	Read once, left to right	Read once, left to right	On the tape, readable many times
Can write	No	Push and pop	Any cell
Always halts	Yes	Can be arranged	No
Languages	Regular	Context-free	Recursively enumerable

Example: binary increment. Start with the head on the leftmost bit. Move right to the end of the number, then go left, turning trailing 1s into 0s, until a 0 or a blank can become a 1:

State	Read	Write	Move	Next state	Meaning
s0	0	0	R	s0	Scan right to the end
s0	1	1	R	s0
s0	B	B	L	s1	Past the end: go back to the last bit
s1	1	0	L	s1	1 + 1 = 10: write 0, carry left
s1	0	1	L	s2	Absorb the carry: done
s1	B	1	L	s2	Carry out of the top: a new leading 1

s2 has no transitions, so the machine halts when it gets there.

A recognizer for {aⁿbⁿcⁿ}. This language is not context-free, but a TM handles it by crossing off symbols. Replace the first a by X, scan right to the first b and replace it by Y, then the first c by Z, and return to the left. Repeat until no a remains, then check that only Ys and Zs are left. Each pass costs O(n) steps, and there are n/3 passes, so the time is O(n²).

Robustness. Many variations give exactly the same computable functions. Their speed differs only polynomially, which is why complexity classes such as P (10.3) do not depend on the model:

Variant	Same power?	Cost of simulating it on a standard TM
Tape infinite in one direction only	Yes	Constant factor
Several tapes	Yes	Quadratic
Nondeterministic	Yes	Exponential (whether polynomial suffices is the P vs NP question, 10.3)
Only the symbols 0, 1, B	Yes	Constant factor (encode larger symbols in binary)
PDA with two stacks	Yes	Constant factor: the tape left of the head is one stack, the rest is the other
Unrestricted (type 0) grammars	Yes	They generate exactly the languages TMs recognize

The universal Turing machine. A Turing machine is a finite table, so it can be encoded as a string ⟨T⟩ and written on a tape. Turing showed that there is a single universal machine U that, given ⟨T⟩ and w, simulates T on w. This is the stored-program idea that every computer is built on: one fixed piece of hardware runs any program supplied as data. An interpreter is a universal machine for its language.

def run_tm(rules, tape_text, state="s0", blank="B", max_steps=10_000, trace=False):
    """Simulate a Turing machine. rules maps (state, symbol) to (new state, write, move).
    The machine halts when no rule applies."""
    tape = dict(enumerate(tape_text))                # sparse tape: missing cells are blank
    head = steps = 0
    while (state, tape.get(head, blank)) in rules:
        if trace:
            print(show(tape, head, state, blank))
        if steps == max_steps:
            raise RuntimeError("no halt within the step budget")   # we cannot tell whether it ever would
        new_state, write, move = rules[state, tape.get(head, blank)]
        tape[head] = write
        head += 1 if move == "R" else -1
        state, steps = new_state, steps + 1
    if trace:
        print(show(tape, head, state, blank), "(halted)")
    used = [i for i, ch in tape.items() if ch != blank]
    content = "".join(tape.get(i, blank) for i in range(min(used), max(used) + 1)) if used else ""
    return state, content, steps

def show(tape, head, state, blank):
    lo, hi = min(min(tape, default=0), head), max(max(tape, default=0), head)
    cells = "".join(f"[{tape.get(i, blank)}]" if i == head else tape.get(i, blank) for i in range(lo, hi + 1))
    return f"{state}: {cells}"

increment = {
    ("s0", "0"): ("s0", "0", "R"), ("s0", "1"): ("s0", "1", "R"), ("s0", "B"): ("s1", "B", "L"),
    ("s1", "1"): ("s1", "0", "L"), ("s1", "0"): ("s2", "1", "L"), ("s1", "B"): ("s2", "1", "L"),
}
run_tm(increment, "1011", trace=True)
# s0: [1]011
# s0: 1[0]11
# s0: 10[1]1
# s0: 101[1]
# s0: 1011[B]
# s1: 101[1]B
# s1: 10[1]0B
# s1: 1[0]00B
# s2: [1]100B (halted)

for n in ["111", "0", "", "100111"]:
    print(repr(n), "→", run_tm(increment, n)[1:])
# '111' → ('1000', 8)
# '0' → ('1', 3)
# '' → ('1', 2)
# '100111' → ('101000', 11)

Analogy. A Turing machine is a clerk working through an infinitely long ledger with a rule book. The clerk looks at one entry, consults the rule book for their current "mode" and that entry, erases or writes, turns one page left or right, and changes mode. The rule book is finite, but the ledger never runs out.

Key takeaways

• A Turing machine is a finite control plus an unbounded tape that it can read, write, and move along in both directions.
• It halts when no transition applies, and it may run forever. That possibility is the source of undecidability.
• Multiple tapes, nondeterminism, smaller alphabets and two-stack PDAs all have the same power, with at most polynomial slowdown, except that nondeterminism costs exponential time in known simulations.
• Unrestricted grammars generate exactly the languages that Turing machines recognize.
• A universal TM simulates any TM from its description. This is the theory behind stored-program computers and interpreters.

Practice

1. (Beginner) Trace the increment machine on 0111 and count the steps. How many steps does it take on 1ⁿ (n ones), as a function of n?
2. (Intermediate) Design a Turing machine that decides {aⁿbⁿ : n ≥ 0}: it must halt in an accepting state on members and in a rejecting state on all other strings over {a, b}. Run it with run_tm and estimate its running time as a function of n.
3. (Interview) Explain why a finite automaton with two stacks is as powerful as a Turing machine, while one stack is not. Hint: store the tape left of the head on one stack and the tape from the head rightwards on the other. Moving the head is a pop from one stack and a push onto the other. With one stack, information below the top is lost once it is popped, and the pumping lemma for context-free languages limits what can be recognized.

Church–Turing Thesis

Why. To prove that "no algorithm can solve problem X", we need a precise definition of "algorithm". Without one, a skeptic can always reply "maybe a cleverer kind of procedure could". The Church–Turing thesis is the bridge between the informal idea of an algorithm and a mathematical definition. Every impossibility result in computer science rests on it.

What.

Church–Turing thesis. Every function that can be computed by an effective procedure (an algorithm: a finite list of precise, mechanical instructions that a person could follow with pencil and paper, given unlimited time and paper) can be computed by a Turing machine.

It is a thesis, not a theorem. "Effective procedure" is an informal idea, so the statement cannot be proved, only supported by evidence. The evidence is strong:

1. Independent models agree. In the 1930s, several very different definitions of "computable" were proposed: Church's λ-calculus, Gödel and Herbrand's general recursive functions, Turing machines and Post's production systems. They were all proved to define exactly the same class of functions. Every model proposed since then has either matched this class or been weaker.
2. Turing's analysis. Turing argued directly that any step-by-step human computation (finitely many states of mind, finitely many symbols observable at once, local changes) can be imitated by his machines.
3. No counterexample. In about 90 years, nobody has found a procedure that is accepted as an algorithm but cannot be carried out by a Turing machine.

Turing completeness. A system is Turing complete if it can simulate any Turing machine. By the thesis, it can then compute anything that is computable at all. Turing completeness turns up in surprising places:

Turing complete	Not Turing complete (by design)
Every general-purpose programming language	Regular expressions without backreferences (13.3)
Minsky register machines with just two counters	Context-free grammars (13.1)
Conway's Game of Life and the cellular automaton Rule 110	Plain SQL queries (relational algebra), without recursion
C++ templates, and the x86 mov instruction alone	Total languages (Coq, Agda, Dhall), where every program provably terminates
Magic: The Gathering, with a contrived card setup	Loops with a bound fixed when the loop starts (the "LOOP" language)

Being less than Turing complete is often a feature. If every program terminates and its behavior can be analyzed, then configuration files, database queries, smart contracts and packet filters become safer and more predictable. This is the "rule of least power". Accidental Turing completeness, as in template systems or document formats, makes static analysis impossible in general (next topics) and can turn a "data" format into an attack surface.

Variants of the thesis.

Thesis	Claim	Status
Church–Turing	Effectively computable = Turing computable	Universally accepted
Physical Church–Turing	Every function computable by a physical device is Turing computable	Widely believed. Quantum computers compute the same functions as TMs
Extended (strong) Church–Turing	Every reasonable model can be simulated by a TM with only polynomial slowdown	Challenged by quantum computing: Shor's factoring algorithm is polynomial on a quantum computer, while no classical polynomial algorithm is known

Example: a minimal Turing-complete model. A Minsky register machine has a few registers holding natural numbers and only two instructions: increment a register, and "decrement unless zero, otherwise jump". That is enough to compute every computable function (with two registers, given a suitable encoding of the input). The programs below are therefore as expressive, in principle, as any Python program.

def run_rm(program, registers, max_steps=10**6):
    """Minsky register machine. Instructions, addressed by index:
       ("inc", r, next)              r += 1, then go to next
       ("dec", r, next, if_zero)     if r > 0: r -= 1 and go to next, else go to if_zero
    The machine halts when it jumps to the label "halt"."""
    regs, pc = dict(registers), 0
    for _ in range(max_steps):
        if pc == "halt":
            return regs
        op = program[pc]
        if op[0] == "inc":
            regs[op[1]] = regs.get(op[1], 0) + 1
            pc = op[2]
        elif regs.get(op[1], 0) > 0:
            regs[op[1]] -= 1
            pc = op[2]
        else:
            pc = op[3]
    raise RuntimeError("step budget exhausted")      # might halt later, might never: we cannot tell

# c := a + b   (empties a and b)
add = [("dec", "a", 1, 2), ("inc", "c", 0),
       ("dec", "b", 3, "halt"), ("inc", "c", 2)]

# c := a · b   (for each unit of a, add b to c, using t to restore b afterwards)
mul = [("dec", "a", 1, "halt"),     # 0: take one unit from a, or stop
       ("dec", "b", 2, 4),          # 1: move b into t, adding 1 to c each time
       ("inc", "c", 3),             # 2
       ("inc", "t", 1),             # 3
       ("dec", "t", 5, 0),          # 4: move t back into b, then repeat from 0
       ("inc", "b", 4)]             # 5

print(run_rm(add, {"a": 3, "b": 4}))    # {'a': 0, 'b': 0, 'c': 7}
print(run_rm(mul, {"a": 6, "b": 7}))    # {'a': 0, 'b': 7, 'c': 42, 't': 0}

Analogy. The thesis is like a law of physics. It is a claim about the world (here, about what "mechanical procedure" means) backed by every experiment so far, not a theorem derived from axioms. One genuinely new kind of algorithm would refute it, and none has appeared in nine decades.

Key takeaways

• The Church–Turing thesis says that "computable by an algorithm" means "computable by a Turing machine". It is a well-supported definition, not a provable theorem.
• Its evidence: very different models (λ-calculus, recursive functions, TMs, register machines, programming languages) all compute exactly the same functions.
• Turing complete means able to simulate any TM. It is easy to achieve, even by accident.
• Deliberately non-Turing-complete languages trade expressiveness for guaranteed termination and analyzability.
• Quantum computers do not violate the thesis, but they may violate its extended, efficiency-based version.

Practice

1. (Beginner) Write register-machine programs for (a) b := a while leaving a unchanged, using a temporary register; (b) c := max(a − b, 0) (truncated subtraction). Test them with run_rm.
2. (Intermediate) In the "LOOP" language, the only loop is repeat x times { … }, where the count is fixed when the loop starts. Explain why every LOOP program halts, and why this means some computable function cannot be written in LOOP. Hint: list all LOOP programs (they are strings, 2.3) and diagonalize: define g(n) = Pₙ(n) + 1. The Ackermann function is a natural example.
3. (Interview) Your team is designing a rules language for customers to customize pricing. One engineer wants it to be a full scripting language, another wants something much more restricted. What questions decide this, and what safeguards would you need if it is Turing complete? Hint: consider guaranteed termination, static validation of rules before deployment (impossible in general for Turing-complete rules, as the next topics show), and resource limits such as step budgets ("fuel" or "gas"), timeouts and sandboxing.

Decidability

Why. With a precise model of computation, "can a computer solve this problem?" becomes a mathematical question. The answer has three levels, not two. Some problems always get an answer. For others, a "yes" can always be confirmed but a "no" may never arrive. For still others, not even that is possible. Knowing which level a problem is on tells you whether to look for an algorithm, settle for a search with a timeout, or redesign the problem.

What. A decision problem is a question with a yes/no answer for each instance: "is n prime?", "does this grammar generate this string?". Instances are encoded as strings (⟨x⟩ denotes the encoding of x), so a decision problem is the language of its yes-instances (13.1).

• A Turing machine decides L if it halts on every input, accepting the strings in L and rejecting the others. L is then decidable (or recursive).
• A Turing machine recognizes L if it accepts exactly the strings in L. On strings outside L it may reject or run forever. L is then recognizable (semi-decidable, or recursively enumerable, because a program can list its members).
• L is co-recognizable if its complement L̄ is recognizable.

Theorem. L is decidable if and only if both L and L̄ are recognizable.

Proof. (⇒) A decider recognizes L. Swapping its accept and reject answers gives a decider for L̄. (⇐) Run the two recognizers in alternation, one step of each in turn (dovetailing). Every w is in L or in L̄, so one of them eventually accepts, and that answers the question.

  ◀─────────── recognizable (RE) ────────────▶
                         ◀──────────── co-recognizable (co-RE) ─────────────▶
  ┌──────────────────────┬───────────────────┬──────────────────────────────┐
  │ HALT                 │ decidable         │ complement of HALT           │
  │ "M accepts           │ = RE ∩ co-RE      │ "M accepts no input"         │
  │  some input"         │ regular, CFLs, P  │                              │
  └──────────────────────┴───────────────────┴──────────────────────────────┘

  Outside both:  TOTAL = { ⟨M⟩ : M halts on every input }

What is decidable for each model. The same question can be decidable for a weak model and undecidable for a strong one:

Question	DFA / regular expression	CFG / PDA	Turing machine / program
Is w ∈ L?	Decidable, O(n)	Decidable, O(n³)	Recognizable, undecidable
Is L empty?	Decidable (reachability)	Decidable	Undecidable, not even recognizable
Is L finite?	Decidable	Decidable	Undecidable
Is L = Σ*?	Decidable	Undecidable	Undecidable
Is L₁ = L₂?	Decidable (minimal DFAs)	Undecidable	Undecidable
Is the grammar ambiguous?	—	Undecidable	—

Reductions. To show that a problem B is undecidable, show that a decider for B would give a decider for a problem A that is already known to be undecidable. A (mapping) reduction A ≤ B is a computable function g with w ∈ A ⇔ g(w) ∈ B for all w.

• If A ≤ B and B is decidable, then A is decidable: compute g(w), then run the decider for B.
• Contrapositive: if A ≤ B and A is undecidable, then B is undecidable.

Note the direction: reduce the known hard problem to the new one. The next topic uses this to spread undecidability from the halting problem.

Rice's theorem (1953). Any non-trivial semantic property of programs is undecidable. "Semantic" means the property depends only on what the program computes (its language or its input/output function), not on how it is written. "Non-trivial" means some programs have the property and some do not. So all of these are undecidable:

• Does this program ever print "hello"?
• Does this function return the same result as that one on every input?
• Does this program halt on every input?
• Is the language this program accepts regular? Empty?

Syntactic properties, such as "does the source contain a while loop?" or "does it have more than 100 lines?", are decidable by reading the text. Rice's theorem is about behavior.

Natural undecidable problems are not only about programs:

Problem	Undecidable since
Hilbert's tenth problem: does a polynomial equation with integer coefficients have an integer solution?	Matiyasevich, 1970 (building on Davis, Putnam and Robinson)
Post's correspondence problem: can domino tiles (uᵢ, vᵢ) be lined up so that the top and bottom strings agree?	Post, 1946
The word problem for finitely presented groups (12.1): do two words denote the same element?	Novikov and Boone, 1950s
Wang tiles: can a finite set of edge-colored tiles tile the whole plane?	Berger, 1966

Semi-decidability in action. "Does p(x, y) = 0 have a solution in natural numbers?" is recognizable: try every pair (x, y) in Cantor's diagonal order (2.3), and stop when one works. If a solution exists, the search finds it. If none exists, the search runs forever, and by Matiyasevich's theorem no cleverer algorithm can always detect that.

from itertools import count

def pairs():
    """Every pair of natural numbers, ordered by x + y: Cantor's diagonal walk (2.3)."""
    for s in count():
        for x in range(s + 1):
            yield x, s - x

def has_solution(p, budget):
    """Recognizer for 'p(x, y) = 0 has a solution in ℕ', cut off after `budget` candidates."""
    for tried, (x, y) in enumerate(pairs()):
        if p(x, y) == 0:
            return "yes", (x, y), tried               # a yes is always found eventually
        if tried == budget:
            return "unknown", None, tried             # a no is never certain: the search just continues

print(has_solution(lambda x, y: x * x + y * y - 25, budget=10**6))
# ('yes', (0, 5), 15)
print(has_solution(lambda x, y: x * x - 13 * y * y - 1 if y > 0 else 1, budget=10**6))
# ('yes', (649, 180), 344684): Pell's equation, whose smallest solution is far out
print(has_solution(lambda x, y: x * x + y * y - 3, budget=10**6))
# ('unknown', None, 1000000): there is no solution, but the search cannot know that

For x² + y² = 3, a human proves there is no solution with a short argument modulo 4 (4.3). For this one family a decider exists. Matiyasevich's theorem says that no single algorithm can find such arguments for every polynomial.

Analogy. A recognizer is a search party looking for a lost hiker. If the hiker is out there, the party will eventually find them. If not, the party never gets to announce "nobody is out there": it can only keep searching or give up without an answer. A decider is a search party with a map showing every place the hiker could be.

Key takeaways

• A decider halts on every input. A recognizer may run forever on non-members.
• L is decidable exactly when both L and its complement are recognizable (run them in alternation).
• Regular and context-free languages have decidable membership. Many other questions (equivalence of CFGs, anything non-trivial about programs) are undecidable.
• Reductions A ≤ B transfer undecidability from A to B. Always reduce the known hard problem to the new one.
• Rice's theorem: every non-trivial question about what a program computes is undecidable. Questions about how the program is written can be decidable.

Practice

1. (Beginner) Decidable, recognizable but undecidable, or neither? (a) Does a given DFA accept some string of even length? (b) Does a given Python program contain the keyword while? (c) Does a given program ever execute the body of a while loop, on empty input? (d) Does a given CFG generate the string abba?
2. (Intermediate) Prove that the decidable languages are closed under union, intersection and complement, and that the recognizable languages are closed under union and intersection. Hint: for the union of recognizable languages, the two recognizers must be run in alternation, not one after the other. Why? Then explain why the recognizable languages are not closed under complement.
3. (Interview) A product manager asks for a linter rule that flags exactly the functions that can raise an unhandled exception, with no false positives and no false negatives. What do you answer, and what can you build instead? Hint: the property is semantic and non-trivial, so Rice's theorem rules it out. Practical tools give up one side: sound over-approximations that flag some safe code (type systems, checked exceptions), or under-approximations that report only certain bugs (pattern-based linters, fuzzing).

Halting Problem

Why. The halting problem is the first problem proved undecidable, and almost every other undecidability result is reduced from it. It also has practical weight. No debugger, compiler or code reviewer can be guaranteed to detect every infinite loop, every unreachable line of code or every malicious program. Tools in all these areas are approximate because of this theorem. A preview of the proof appeared in 1.4. Here it is in full, together with its consequences.

What. The halting problem is the language

  HALT = { ⟨M, w⟩ : M is a Turing machine that halts on input w }

Theorem (Turing, 1936). HALT is recognizable but not decidable.

Recognizable. Simulate M on w with the universal machine (Turing Machines), and accept if the simulation halts.

Not decidable. Suppose some machine H decides HALT: H(⟨M, w⟩) always halts, says "halts" if M halts on w, and says "loops" otherwise. Build a new machine D that, on input ⟨M⟩:

1. runs H on ⟨M, ⟨M⟩⟩, that is, asks whether M halts when given its own description;
2. if H says "halts", loops forever; if H says "loops", halts.

Now run D on its own description ⟨D⟩:

• if D halts on ⟨D⟩, then H said "halts" in step 1, so D loops forever, which is a contradiction;
• if D loops on ⟨D⟩, then H said "loops", so D halts, which is also a contradiction.

So H cannot exist. ∎

It is a diagonal argument. List all machines M₁, M₂, … (they are strings, so they can be listed, 2.3) and tabulate whether Mᵢ halts on ⟨Mⱼ⟩. D is built to do the opposite of the diagonal entry, so it differs from every row. But D is a machine, so it should be one of the rows. This is Cantor's argument (2.3), with "halts / loops" in place of digits:

              ⟨M₁⟩    ⟨M₂⟩    ⟨M₃⟩    ⟨M₄⟩    …
     M₁      [halt]   loop    halt    loop
     M₂       halt   [halt]   halt    halt
     M₃       loop    loop   [loop]   halt
     M₄       halt    loop    loop   [halt]
     ⋮
     D        loop    loop    halt    loop    …     ← flips the diagonal, so D ≠ Mᵢ for every i

Consequences.

• The complement of HALT is not recognizable. HALT is recognizable, and if its complement were too, HALT would be decidable (Decidability).
• Halting on empty input is undecidable. Reduce HALT to it: from ⟨M, w⟩, build the machine M_w that erases its input, writes w and runs M. Then M halts on w ⇔ M_w halts on λ. The same pattern proves Rice's theorem.
• Uncomputable functions. The busy beaver function BB(n) is the largest number of steps that an n-state, 2-symbol Turing machine can take before halting, when started on a blank tape. If BB were computable, we could decide halting on a blank tape: run the machine for BB(n) steps and see. BB therefore grows faster than every computable function. Only a few values are known: BB(5) = 47,176,870 was proved in 2024 by a collaborative, computer-verified project.
• Open problems hide inside. The program "search for an even number > 2 that is not a sum of two primes, and halt if found" halts if and only if Goldbach's conjecture is false. A halting decider would settle Goldbach's conjecture, and many other open problems, mechanically.

What it means in practice.

What you might want	Why it is impossible in general	What practice does instead
Detect every infinite loop	It is HALT	Timeouts, watchdogs, step budgets ("gas")
Remove all dead code	"Is this line reachable?" encodes HALT	Conservative analysis: remove only code that is provably dead
A perfect virus scanner	"Does this program behave maliciously?" is semantic (Rice). Cohen, 1987	Signatures, heuristics, sandboxing, behavior monitoring
Prove every terminating program terminates	Would decide HALT	Termination checkers for restricted programs (ranking functions), or total languages
An optimal compiler (shortest equivalent program)	Program equivalence is undecidable	Heuristic optimization passes

Every such tool must choose to be sound (never miss a problem, at the cost of false alarms) or complete (never raise a false alarm, at the cost of missing problems), and accept that it cannot be both for all programs.

def halts_within(program, arg, budget):
    """Run a step-wise program (a generator function) for at most `budget` steps.
    True: it halted. False: it is still running, which proves nothing about the future."""
    steps = program(arg)
    for _ in range(budget):
        try:
            next(steps)
        except StopIteration:
            return True
    return False

def diagonal(halts):
    """Turing's construction: given any claimed halting decider, build a program that it gets wrong."""
    def d(program):
        if halts(program, program):      # predicted to halt on itself...
            while True:                  # ...so loop forever
                yield
        yield                            # predicted to loop, so halt after one step
    return d

claimed_deciders = {
    "always halts": lambda p, x: True,
    "never halts":  lambda p, x: False,
    "name parity":  lambda p, x: len(p.__qualname__) % 2 == 0,   # an arbitrary "clever" rule
}
for name, halts in claimed_deciders.items():
    d = diagonal(halts)
    print(f"{name:12}  predicts {halts(d, d)!s:5}   actual (10⁴ steps): {halts_within(d, d, 10**4)}")
# always halts  predicts True    actual (10⁴ steps): False
# never halts   predicts False   actual (10⁴ steps): True
# name parity   predicts False   actual (10⁴ steps): True

# A "decider" that works by simulation never answers on d: it waits for d, which waits for it
simulating = lambda p, x: halts_within(p, x, 10**4)
try:
    simulating(diagonal(simulating), diagonal(simulating))
except RecursionError:
    print("the simulating 'decider' never returned")   # it is a recognizer at best, not a decider

Analogy. Imagine a fortune teller who claims to predict whether any person will leave a room within an hour. A contrarian walks in, asks for the prediction about themselves, and does the opposite. No fortune teller, however skilled, survives a customer who can consult the prediction and then act against it. The halting proof builds exactly that customer from the claimed decider.

Key takeaways

• HALT is recognizable (simulate and wait) but not decidable. Its complement is not even recognizable.
• The proof is a diagonal argument: a machine that does the opposite of what the decider predicts about it.
• Undecidability spreads by reduction: halting on empty input, Rice's theorem, program equivalence, reachability of code.
• The busy beaver function is uncomputable and grows faster than any computable function.
• Real tools for termination, dead code and malware are approximations. Each must give up either soundness or completeness.

Practice

1. (Beginner) Explain why "run the program and see whether it stops" gives a recognizer for HALT but not a decider. What does a timeout add, and what can it not add?
2. (Intermediate) Prove that the following are undecidable by reducing HALT to them: (a) "does M halt on the empty input?"; (b) "does program P ever print done?"; (c) "do programs P and Q produce the same output on every input?". Hint: for (b), modify M so that it prints done right before halting and nowhere else. For (c), compare against a program that ignores its input and prints a fixed answer.
3. (Interview) Your team wants a CI check that rejects every pull request introducing a possible infinite loop, with no false alarms. Explain why that is impossible, then design something useful. Hint: any exact check would decide HALT. Practical options: step or time limits in tests, lint rules for specific risky patterns (while True without break), loop bounds or ranking functions for code that must provably terminate, and fuzzing with timeouts. State which side, false alarms or missed loops, each option errs on.