Tag
regular-languages
- Oct 24, 2026 How a DFA Decides Membership: Transition Tables and the Extended Transition Function The five-tuple, the recursive lift of the transition function to whole strings, and the table layouts that make each input symbol cost one dependent load. computation theory
- Aug 2, 2026 Right-Linear Grammars and the Limits of One-Way Derivation Why a grammar whose rules can only consume input left to right generates exactly the regular languages, and what happens to the language when left-linear rules are mixed in. computation theory
- Jun 18, 2026 Simulating an NFA Without Determinizing It: State Sets, Epsilon Closure, and Bitsets How a nondeterministic automaton runs on a single pass by carrying a set of live states, why the closure step dominates the cost, and how bitsets make it cheap. computation theory
- Nov 18, 2025 Distinguishing Strings and the Myhill-Nerode Theorem How the set of right contexts partitions a language into classes, why that partition is exactly the minimal DFA, and how to use it as an upper bound in proofs. computation theory
- May 6, 2025 Where the 2^n Comes From: Subset Construction and the Limits of Determinization Why determinizing an n-state NFA can require exponentially many states, how to exhibit a language that forces the blow-up, and which partial determinization schemes keep it bounded in practice. computation theory