Tag
deterministic-automata
- 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
- Oct 23, 2026 Testing DFA Equivalence with Union-Find Instead of a Product Table Why two machines accept the same language exactly when no reachable pair is split by acceptance, and how merging pairs in a disjoint-set structure avoids building the product. computation theory
- Mar 18, 2025 Differentiating a Regular Expression: Residual Languages as Automaton States How the Brzozowski derivative turns matching into repeated symbolic differentiation, why the residual languages are already DFA states, and where the construction blows up. computation theory
- May 4, 2024 Partition Refinement: Minimizing a DFA by Splitting Blocks How Hopcroft-style minimization refines an initial partition into equivalence classes of states, why splitting the smaller half gives O(n log n), and where the implementation gets it wrong. computation theory
- Mar 10, 2023 Product Constructions: Intersection, Union, and Complement Without Rebuilding How pairing states from two machines computes a boolean operation on their languages, why complement needs a total transition function, and what the product costs in states. computation theory