automata

The naive mask costs 64 million validity checks per response. The trick that made constrained decoding practical is to notice that the answer depends only on the automaton's current state, so it can be computed once per state and looked up thereafter. This lesson builds that idea: regex to DFA, why the state is a sufficient summary, how JSON Schema compiles down, and what the index costs.

Finite memory fails on anything that must be counted, so add memory and watch what each purchase buys. A stack buys nesting and nothing more. An unbounded tape buys everything, and two entirely different formalisms invented in the same year turn out to buy exactly the same thing.

A machine with a fixed number of states can recognise a surprising amount, and then hits a wall that no amount of cleverness moves. This lesson builds the finite automaton, shows that regular expressions are the same thing in different notation, and proves by counting that balanced parentheses are out of reach.

How much computational power does a language need? The Chomsky hierarchy answers it with four nested classes of grammar. This lesson builds the ladder from regular to recursively enumerable, shows the machine that recognizes each rung, and locates human language on it using the classic proof that it is not context-free.