automata-regular-languageslisted
Install: claude install-skill rustcircle/c101
# Automata and regular languages
Constructions and proofs for regular languages, and how they show up in lexers and regex engines.
The Chomsky-hierarchy table stays in `cs-foundations` section 6; writing and debugging real regexes
(flavours, ReDoS fixes) is `regex-engineering`; parser construction is `compiler-construction`.
## 1. Definitions and conversions
- DFA: (Q, Sigma, delta: Q x Sigma -> Q, q0, F). Complete when delta is total; add a dead (sink)
state to complete it.
- NFA: delta: Q x Sigma -> 2^Q; accepts if some run ends in F. epsilon-NFA: transitions on epsilon
too; the epsilon-closure E(S) is everything reachable from S by epsilon moves.
- epsilon-elimination: delta'(q, a) = E(delta(E({q}), a)), and q is accepting if E({q}) meets F.
- All four (DFA, NFA, epsilon-NFA, regular expressions) describe exactly the regular languages
(Kleene's theorem).
| From -> To | Construction | Size bound |
|---|---|---|
| regex (length m) -> epsilon-NFA | Thompson | at most 2m states, one accepting state |
| regex -> epsilon-free NFA | Glushkov / position automaton | (symbol occurrences) + 1 states |
| regex -> DFA directly | Brzozowski derivatives, followpos | up to exponential |
| NFA (n states) -> DFA | subset construction | up to 2^n, and that is tight |
| DFA -> minimal DFA | Hopcroft or Moore | at most n, unique up to renaming |
| automaton -> regex | state elimination | can be exponential |
## 2. Subset construction
DFA states are sets of NFA states: start at E({q