Toc Automata Regex And Parsing

---
name: toc-automata-regex-and-parsing
description: "Use when reasoning about what a language or matcher can express: automata and the Chomsky hierarchy as a practical design tool, DFAs, NFAs and state machines, what regular expressions actually are and what they cannot do, ReDoS and catastrophic backtracking, and parsing and grammar classes (LL, LR, PEG, ambiguity) with the practical points. Includes the router for the whole theory-of-computation reference."
---

# Theory of Computation: Automata, Regular Expressions, and Parsing

> **Part 1 of 5** of the *Theory of Computation* reference (plugin `theory-of-computation`), covering §0–§3. Sibling skills: `toc-computability-and-complexity` (§4–§7), `toc-beyond-np-space-and-distributed-limits` (§8–§11), `toc-type-systems-and-randomization` (§12–§13), `toc-reference` (§14–§19). Section numbers are shared across the set; a reference written as §N → `skill` points into that sibling skill.
>
> **Currency:** Verified August 2026. See §16 → `toc-reference` for the currency snapshot and what goes stale first.

> **How to read this.** Reference, not a course. Three markers:
> - **[DURABLE]** — proven theorems and stable practice. **This is most of the document,
>   and it does not expire.**
> - **[VERSIONED]** — the small moving parts: recent results, solver capability, open
>   problems.
> - **[CONTESTED]** — genuine disagreement, mostly about pedagogy and practical relevance.
>
> **⚠️ GOTCHA** boxes mark places where ignorance of the theory produces a specific,
> expensive production failure — which is the whole argument for learning it.
>
> **The three framings that organize everything below:**
> 1. **This is the only branch of CS that tells you what you cannot do.** Everything else
>    teaches techniques. Theory tells you when to stop looking — and **knowing a problem is
>    undecidable or NP-hard is more valuable than any algorithm**, because it redirects
>    you from an impossible goal to a tractable approximation of it.
> 2. **You already use it; you may not know the names.** Regex is finite automata.
>    Your parser is a pushdown automaton. Your state machine is a DFA. Your build system's
>    cycle detection is graph theory. **The theory isn't an addition to your practice — it's
>    a description of it**, and knowing the description tells you where the edges are.
> 3. **"Hard" is not "impossible," and this is the most consequential practical point.**
>    NP-complete problems with thousands of variables are solved routinely (§9 → `toc-beyond-np-space-and-distributed-limits`). The
>    theory tells you *no algorithm is fast on all inputs* — it says nothing about
>    **your** inputs, which are usually structured. **Treating NP-hardness as a verdict
>    rather than a warning is the single most common misapplication of this material.**

---

## §0. Routing

| Asked about... | Go to |
|---|---|
| Automata, state machines, the Chomsky hierarchy | §1 |
| Regex — capabilities, limits, **and ReDoS** | §2 |
| Parsing, grammars, and why your language is hard to parse | §3 |
| Turing machines, halting, **what static analysis can't do** | §4 → `toc-computability-and-complexity` |
| Complexity classes, P vs NP, reductions | §5 → `toc-computability-and-complexity` |
| **"My problem is NP-hard — now what?"** | **§6 → `toc-computability-and-complexity`** |
| SAT/SMT solvers and constraint solving | §7 → `toc-computability-and-complexity` |
| Beyond NP: PSPACE, EXPTIME, and the hierarchy | §8 → `toc-beyond-np-space-and-distributed-limits` |
| Fine-grained complexity — is my O(n²) optimal? | §9 → `toc-beyond-np-space-and-distributed-limits` |
| Space, memory, streaming | §10 → `toc-beyond-np-space-and-distributed-limits` |
| Distributed systems impossibility results | §11 → `toc-beyond-np-space-and-distributed-limits` |
| Type systems, Curry–Howard, verification | §12 → `toc-type-systems-and-randomization` |
| Randomness, approximation, heuristics | §13 → `toc-type-systems-and-randomization` |
| "Don't do this" | §14 → `toc-reference` |
| "Which side is right?" | §15 → `toc-reference` |
| "Is this still current?" | §16 → `toc-reference` |
| Books and courses | §17 → `toc-reference` |

---

## §1. Automata and the Chomsky Hierarchy

### 1.1 The hierarchy as an engineering tool

**[DURABLE] The most practically useful idea in this entire document**: languages form a
strict hierarchy, each level needs strictly more machine, and **recognizing which level
your problem sits at tells you immediately what tool to use and what will never work.**

```
                        MACHINE              MEMORY            YOU MEET IT AS
Regular          ←  finite automaton     none (fixed states)   regex, lexers, protocol
                                                               state machines, UI states
Context-free     ←  pushdown automaton   a stack               programming language syntax,
                                                               JSON/XML nesting, expressions
Context-sensitive←  linear-bounded TM    bounded tape          type checking, most "real"
                                                               language rules
Recursively      ←  Turing machine       unbounded tape        general computation
enumerable
                                          ↑ everything above this line is decidable-ish
                                            below it, see §4
```

**[DURABLE] The pumping lemma is the tool for proving something is *not* at a level**, and
the engineering translation is simple: **a finite automaton cannot count unboundedly.**
That single fact is why `a^n b^n` isn't regular, why balanced parentheses aren't regular,
and why the answer to "can I match nested HTML with a regex?" is **no, and it is not a
matter of cleverness** (§2.2).

### 1.2 DFAs, NFAs, and state machines

**DFA**: one state at a time, one transition per input symbol. **NFA**: may be in many
states at once, may have ε-transitions. **[DURABLE] They recognize exactly the same
languages** — every NFA has an equivalent DFA (subset construction), **at a worst-case
exponential blowup in state count.** That blowup is not theoretical trivia; it's why some
regex engines compile lazily and why a pathological pattern can explode.

**Where you actually use this:**
- **Explicit state machines** — order lifecycle, connection state, UI flows, protocol
  handling. **[DURABLE] Model these as an explicit DFA with enumerated states and
  transitions**, not as a pile of boolean flags. The flags approach fails the moment you
  have a state combination nobody enumerated, and it fails silently.
- **Lexers/tokenizers** — a DFA over character classes.
- **Protocol validation** — is this message sequence legal?
- **Model checking** — verifying that a system's state graph satisfies a property.

**Composition matters**: regular languages are closed under union, intersection,
complement, concatenation, and star. **[DURABLE] Closure under intersection and complement
is what makes automata composable as a specification language** — you can build "matches A
but not B" mechanically.

---

## §2. Regular Expressions in Practice

### 2.1 What regex actually is

**[DURABLE] Theoretical regular expressions and "regex" as implemented are different
things.** Backreferences (`\1`), lookahead/lookbehind, and recursion are **not regular** —
they push the language beyond finite automata, which is exactly why they cost more.

**Two engine families, and the distinction matters enormously:**

| Engine | How | Consequence |
|---|---|---|
| **Backtracking** (PCRE, Perl, Python `re`, Java, JavaScript, .NET) | Explores alternatives, backs up on failure | Supports backreferences and lookaround. ⚠️ **Worst case exponential** — §2.3 |
| **Automata-based** (RE2, Rust `regex`, Go `regexp`, `grep -E` typically) | Simulates an NFA/DFA | **Linear-time guaranteed.** No backreferences |

**[DURABLE] If you are matching untrusted input, this is a security decision, not a style
preference.**

### 2.2 What regex cannot do

**⚠️ Nested structures.** HTML, JSON, balanced parentheses, arbitrary nesting — **regex
cannot match these, ever, because they are context-free and regex is regular** (§1.1).
The famous Stack Overflow answer about parsing HTML with regex is memorable but the
underlying point is a theorem, not an opinion. **Use a parser** (§3).

**⚠️ Counting, arithmetic, and correlated constraints** across arbitrary distance.

### 2.3 ReDoS — where the theory bites daily

> **⚠️ GOTCHA — catastrophic backtracking is a real, common, and preventable denial-of-
> service vulnerability**, and it is the single most direct way automata theory shows up in
> a production incident.
>
> A backtracking engine on a pattern with **nested quantifiers over overlapping
> alternatives** — the `(a+)+`, `(a|a)*`, `(a*)*` shapes — can take **exponential time** on
> a non-matching input, because the number of ways to partition the string explodes.
> A pattern that looks fine and passes tests can be hung by a 30-character string.
>
> **The defences, in order of preference:**
> 1. **Use a linear-time engine** (RE2, Rust `regex`, Go `regexp`) for anything touching
>    untrusted input. This eliminates the class.
> 2. **Avoid nested quantifiers over overlapping alternations.** Learn to recognize the
>    shape.
> 3. **Impose a timeout and an input length cap.**
> 4. **Scan your patterns** — static ReDoS analyzers exist and are worth wiring into CI.
> 5. **Don't build regexes from user input.** That's injection with extra steps.

**[DURABLE] Anchor your patterns.** `^...$` is both a correctness and a performance
property. And **prefer a parser to a heroic regex** — a regex you can't read is a
maintenance liability regardless of complexity class.

---

## §3. Parsing and Grammars

### 3.1 The grammar classes you'll meet

```
Regular           ⊂  LL(k)  ⊂  LR(k)  ⊂  Context-free  ⊂  Context-sensitive
                     ↑          ↑          ↑
                  recursive  most parser  ambiguity possible;
                  descent    generators   general parsers (Earley, GLR, CYK)
                  by hand    (yacc, etc.) handle it at higher cost
```
**LL(k)** parses top-down with k symbols of lookahead — **this is what hand-written
recursive descent is**, and it's why hand-written parsers are common and pleasant.
**⚠️ LL cannot handle left recursion** (`expr := expr '+' term` loops forever); you rewrite
it iteratively.
**LR(k)** parses bottom-up, handles a strictly larger class, and is what parser generators
emit. **LALR** is the compressed variant most tools actually use — and **"shift/reduce
conflict" means your grammar isn't in the class the tool handles**, which is the theory
telling you something real.
**PEG / packrat** — ordered choice removes ambiguity by fiat, which is convenient and
occasionally hides a genuine grammar problem.

### 3.2 The practical points

**[DURABLE] Real programming languages are not context-free**, and this surprises people.
Declaration-before-use, type correctness, and scope rules are context-sensitive.
**The universal solution: parse the context-free skeleton, then do semantic analysis on the
tree.** That two-phase structure is not an implementation convenience; it's a direct
consequence of where the language sits in the hierarchy.

**⚠️ C's famous ambiguity** — `x * y;` is either a multiplication or a pointer declaration
depending on whether `x` is a type — requires feeding symbol-table information back into
the parser. **The "lexer hack."** It's ugly because the language design outran the grammar
class.

**[DURABLE] Ambiguity is a property of the grammar, not the language**, and determining
whether an arbitrary CFG is ambiguous is **undecidable** (§4 → `toc-computability-and-complexity`). This is why parser
generators report conflicts rather than proving your grammar unambiguous.

**Practical advice**: **don't hand-roll a parser for a format that has one.** Use a real
JSON/YAML/CSV parser — the edge cases (escaping, encodings, numeric precision, YAML's
famous surprises) have consumed more engineering time collectively than almost any other
category of self-inflicted bug.