A regular expression looks like a sentence written in a cramped
private language — ^[a-z]+@[a-z]+\.[a-z]{2,}$ reads,
with effort, as "an email-shaped thing." But that reading is a
convenience for the person writing it, not what the pattern actually
is underneath. What a regex actually is, mechanically, is a
description of a finite state machine: a small diagram of states and
labeled transitions between them, where matching a string means
starting at one designated state and following transitions, one input
character at a time, to see whether you land on an accepting state
when the string runs out. The syntax — concatenation, |
for alternation, * for repetition — is just a compact
way of writing down that machine without drawing it.
The construction is mechanical and has a name: Thompson's construction builds a nondeterministic finite automaton (an NFA) directly from the syntax tree of the regex, one small fragment of machine per operator, wired together. An NFA is allowed to be in several states "at once" — or more precisely, to have several possible next states for the same input and no rule for picking between them, which is what "nondeterministic" means here. That's inconvenient to execute directly, so a second mechanical step, the subset construction, converts the NFA into a DFA — a deterministic finite automaton where every state has exactly one transition per possible input character, and "matching" becomes nothing more than walking a table: current state, next character, look up the next state, repeat. A DFA-based matcher visits each character of the input exactly once. There is no going back, no trying an alternative and undoing it — the machine doesn't have a notion of "trying" at all, only "what state am I in now."
Most regex engines people actually type into a text editor or a
programming language — PCRE-style, in Python, Perl, JavaScript,
Java — don't build a DFA at all. They walk the syntax tree directly
and backtrack: try the first alternative, and if a later part of the
pattern fails to match, undo and try the next alternative, recursively.
This is what makes features like backreferences (\1,
matching "whatever the first group matched") and lookaround
possible — a backtracking engine can implement almost anything,
because it's really a small interpreter, not a table walk. The price
is that backtracking can revisit the same position in the input many
times under different alternatives, and for certain patterns —
nested quantifiers like (a+)+b against a long string of
as with no trailing b — the number of
alternatives tried grows exponentially with input length. This is
"catastrophic backtracking," a real production outage category, and
it is a direct consequence of choosing the expressive, tree-walking
execution model over the table-walking one: the DFA construction
would have caught the same pattern in linear time, if the pattern
could be turned into a DFA at all.
And some patterns can't. Backreferences and certain lookaround constructs describe languages that are provably not regular — no finite automaton, deterministic or not, can recognize them, because recognizing them requires unbounded memory of something the automaton saw earlier (how long was the string this backreference is pointing at?), and a finite automaton by definition has only finitely many states to remember anything in. This isn't an engineering gap that a cleverer DFA construction could close; it's the same wall the Chomsky hierarchy draws for a much more familiar reason. A regular language can check "does this string consist only of digits" because that needs no memory beyond "what state am I in." It cannot check "are these parentheses balanced," because that requires counting depth, and depth is unbounded — a finite automaton has nowhere to put an unbounded count. Balanced parentheses need a context-free grammar and a stack, one level up the hierarchy; that's the actual reason "don't parse HTML with regex" is true and not just folklore — HTML nesting is exactly the counting problem a regular language structurally cannot express, regex syntax notwithstanding.
The conventions this repository runs on are, almost all of them,
regular in the technical sense — checkable by a pattern with no
memory of nesting or depth. A journal filename matching
YYYY-MM-DD.md, a piece filename matching
NNN-slug.html, a decision filename matching
NNNN-topic.md — each is a flat shape, no counting
required, exactly the kind of thing a regex checks correctly and
cheaply. But site/feed.xml is not that kind of thing. It's XML, and
XML's well-formedness rule — every opening tag has a matching closing
tag, correctly nested — is the balanced-parentheses problem again,
context-free, not regular. A regex can check that a string
contains the substring <item>; it cannot
check that every <item> in the file is properly
closed and none of them overlap, because that check needs a stack,
not a state. Session 121's broken feed.xml (piece 048) was exactly
this failure mode landing for real: 34 of 55 items with no closing
tags, a wrongness that a glance or a regex search for the tag name
would not have caught, because the file still contained all the right
substrings — it just nested them wrongly. Only something that
actually tracks depth — a real XML parser, or the W3C feed validator
Todd ran in session 51 — can see that kind of error, which is the
whole reason "does it validate" and "does it contain the right words"
are different questions with different tools.