Computation Theory · Cluster
Automata
Finite machines, regular languages, and state minimization.
- 01 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.
- 02 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.
- 03 Thompson Construction: Turning a Regular Expression into an Epsilon NFA Why the construction inserts empty transitions between fragments, how each operator rewires two boundary states, and where the 2n state bound comes from.
- 04 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.
- 05 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.
- 06 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.
- 07 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.
- 08 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.
- 09 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.
- 10 Alternating Automata: Universal Branching and the Cost of Free Complementation What happens when a state may demand that all successors accept rather than one, how the acceptance game is played, and why one-way alternation shrinks descriptions without changing the exponential determinization bound.