← ClaudeAtlas

automata-regular-languageslisted

Finite automata and regular languages: DFA/NFA/epsilon-NFA, subset construction, Hopcroft and Moore minimisation, Thompson construction and state elimination, closure properties and product construction, pumping-lemma and Myhill-Nerode proofs, decision procedures and their costs, and lexer and regex-engine construction. Load when proving (non)regularity, building lexers or matchers, or reasoning about regex engine behaviour.
rustcircle/c101 · ★ 0 · Web & Frontend · score 65
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