Automata & Formal Languages · Instrument 06 · Field Notes
From theory to working systems
Automata theory is not just a museum of little machines. It is a map for choosing memory, proving limits, building parsers, and debugging pattern matchers. This epilogue adds the practical heuristics I wish every course made explicit.
Machine chooser
Compiler pipeline
Closure laws
State explosion
Choose a language
A useful rule of thumb: ask what memory the language forces. No memory beyond a state? regular. Nested matching? stack. Multiple unbounded comparisons or arbitrary simulation? tape. A question about all programs? expect undecidability.
machine chooser
Pipeline phase
phase2
Real language tooling layers machines. A lexer is usually regular. A parser is usually context-free-ish. Type checking and semantic analysis need richer computation. Keeping those layers separate is a power move.
lexer -> parser -> semantics
Operation
Closure properties are debugging tools. If a class is closed under an operation, you can transform machines safely. If it is not, the missing closure often tells you exactly why an attempted design feels slippery.
closure laws as engineering moves
NFA size
states8
Engine
The theory warning that matters in practice: compact descriptions can expand violently. NFA-to-DFA conversion can cost 2^n states; backtracking regex engines can revisit the same choices many times unless constrained.