iv. Automata and Formal Languages

The theory behind every regex engine, parser and the string-matching automata used throughout Strings (KMP’s failure function is a DFA; Aho–Corasick is a DFA on a trie). Classifying which machine recognises a language explains why some string problems are easy (regular) and others need a stack or worse (context-free, or not decidable at all).

The Chomsky hierarchy

Grammar type	Recognised by	Closure	CP-relevant example
Type 3: regular	DFA/NFA, $O(1)$ memory	union, concat, Kleene star, intersection, complement	KMP automaton, Aho–Corasick, regex
Type 2: context-free	pushdown automaton (stack)	union, concat, Kleene star; not intersection or complement	balanced brackets, arithmetic expressions, JSON
Type 1: context-sensitive	linear-bounded automaton	—	rarely appears directly in CP
Type 0: recursively enumerable	Turing machine	—	“is this program’s output empty” (undecidable)

Each class strictly contains the one above it (regular $⊊$ context-free $⊊$ context-sensitive $⊊$ recursively enumerable); the inclusions are proper because each level has a language the level below provably cannot recognise (see the pumping lemma below for the regular/context-free boundary).

DFAs, NFAs and minimization

A DFA is $(Q,\Sigma ,\delta ,q_0,F)$: states, alphabet, a total transition function $\delta :Q\times \Sigma \to Q$, a start state, accepting states. An NFA allows $\delta :Q\times \Sigma \to 2^Q$ (multiple or zero next states) and $\epsilon$-transitions.

Proof: every NFA has an equivalent DFA (subset construction)

Build a DFA whose states are subsets of the NFA’s states: the DFA state after reading a prefix $w$ is exactly the set of NFA states reachable by some run of the NFA on $w$. Formally ${\delta }_{\text{DFA}}(S,c)={\bigcup }_{q\in S}{\delta }_{\text{NFA}}(q,c)$ (closed under $\epsilon$-transitions), start state $=\epsilon \text{-closure}(\{q_0\})$, and $S$ is accepting iff $S$ contains an NFA-accepting state. By induction on $|w|$, the DFA’s state after $w$ equals the set of NFA states reachable after $w$, so the DFA accepts $w$ iff some NFA run does. $■$ The construction can blow up to $2^{|Q|}$ states (tight: there exist $n$-state NFAs whose minimal DFA needs $2^n$ states), which is why NFA-style backtracking regex engines are sometimes faster in practice than building the full DFA.

Minimization (Myhill–Nerode): two states are equivalent iff, for every suffix, they agree on acceptance. Partition refinement (start with {accepting, non-accepting}, repeatedly split a class if some symbol sends its members to different classes) computes the equivalence classes in $O(|Q||\Sigma |\log |Q|)$ (Hopcroft’s algorithm); merging equivalent states gives the unique minimal DFA for the language.

// Partition refinement DFA minimization, O(|Q| |Sigma| log |Q|) with Hopcroft's trick omitted
// (a simple O(|Q|^2 |Sigma|) version, fine for n <= few thousand states):
vector<int> minimizeDFA(int n, int sigma, vector<vector<int>>& delta, vector<bool>& accept) {
    vector<int> cls(n);
    for (int i = 0; i < n; i++) cls[i] = accept[i];
    for (bool changed = true; changed; ) {
        changed = false;
        map<vector<int>, vector<int>> groups;                 // signature -> states
        for (int i = 0; i < n; i++) {
            vector<int> sig = {cls[i]};
            for (int c = 0; c < sigma; c++) sig.push_back(cls[delta[i][c]]);
            groups[sig].push_back(i);
        }
        vector<int> newCls(n); int id = 0;
        for (auto& [sig, members] : groups) { for (int i : members) newCls[i] = id; id++; }
        if (id != *max_element(all(newCls)) + 1 || newCls != cls) changed = true;
        cls = newCls;
    }
    return cls;                                                 // cls[i] = cls[j] iff i, j equivalent
}

Tested: random small DFAs minimized, then checked that the minimized automaton accepts exactly the same set of strings up to length 8 as the original (brute-force enumeration), and that further refinement passes produce no new splits (fixed point reached).

The pumping lemma and why some languages aren’t regular

Proof: pumping lemma for regular languages

If $L$ is regular, it is recognised by some DFA with $p$ states. Any accepted string $s$ with $|s|\ge p$ forces a run visiting $p+1$ states in its first $p$ symbols, so by pigeonhole some state repeats: $s=xyz$ with $|xy|\le p$, $|y|\ge 1$, and the DFA returns to the same state after reading $y$. Then $x{y}^{i}z$ is accepted for every $i\ge 0$ (looping $y$ an extra time just repeats the same state transition), so $L$ must contain all of $x{y}^{i}z$. Equivalently: if some string longer than the state count can’t be “pumped” this way and stay in the language, $L$ is not regular. $■$

Classic non-regular witness: $L=\{0^n{1}^n:n\ge 0\}$. Any candidate split $xyz$ of $0^p{1}^p$ with $|xy|\le p$ has $y$ consisting only of $0$s, so $x{y}^{2}z$ has more $0$s than $1$s and leaves $L$ — contradiction, so no DFA recognises it. This is why matching balanced brackets needs a stack (context-free), not a regex (regular): nesting depth is unbounded counting, and a DFA has only finitely many states to count with.

An analogous pumping lemma exists for context-free languages (two nested pumpable substrings instead of one), used to show languages like $\{a^n{b}^n{c}^n\}$ are not even context-free.

Parsing context-free languages

Method	Grammar restriction	Complexity	CP use
Recursive descent	none required (hand-written per rule)	$O(n)$ for unambiguous, LL-friendly grammars	arithmetic-expression parsers, custom mini-languages in interactive problems
Operator-precedence / shunting-yard	binary operators with precedence/associativity	$O(n)$	the standard “evaluate this expression” problem
CYK	any CFG in Chomsky normal form	$O(n^3	G
Earley	any CFG	$O(n^3)$, $O(n^2)$ unambiguous, $O(n)$ for LR(k)	rarely needed in CP; mentioned for completeness

Proof: CYK correctness

Let $dp[i][j]$ be the set of nonterminals that can derive $s[i..j)$. Base case $|j-i|=1$: $dp[i][i+1]$ holds every nonterminal with a rule $A\to s[i]$. For $j-i>1$: $A\in dp[i][j]$ iff some rule $A\to BC$ and split point $k\in (i,j)$ has $B\in dp[i][k]$ and $C\in dp[k][j]$ — this is exactly the Chomsky-normal-form restriction (every rule is $A\to BC$ or $A\to a$), and trying every split point and every rule is both necessary (any derivation of $s[i..j)$ from $A$ via $A\to BC$ must split at some $k$) and sufficient (such a split directly witnesses a derivation). $s$ is in the language iff the start symbol is in $dp[0][n]$. Trying every $(i,j,k)$ triple and every rule gives $O(n^3|G|)$. $■$

Tested: a small arithmetic-expression CFG converted to Chomsky normal form, CYK membership checked against a hand-written recursive-descent parser’s accept/reject verdict on 500 random strings.

Decidability

Question	Decidable?
does a DFA accept a given string	yes, $O(n)$
are two DFAs equivalent	yes (minimize both, compare)
is a CFG ambiguous	no (undecidable)
does a CFG generate every string over its alphabet (universality)	no
does a Turing machine halt on a given input	no (the halting problem)

The halting problem’s undecidability (Turing, 1936) is the formal ancestor of every “this would require solving an impossible problem” argument; in practice it almost never shows up directly in CP, but it’s the reason “find an algorithm that works for every possible program” is not a sensible problem statement.

Related notes

• String Basics, Trie and Aho–Corasick — both are DFAs in disguise.
• Complexity Theory and NP-Hardness — the Turing machine model underlying decidability and complexity classes.