Theory of Computation · topic
DFA, NFA and epsilon-NFA as tuples with acceptance, complete versus partial DFAs, the subset construction with its 2^n bound and tight witness, product construction for union, intersection and difference, minimisation by partition refinement and table filling, state counts for divisibility, substring, prefix, suffix and length conditions, and Moore and Mealy machines.
The formal definitions of DFA, NFA and epsilon-NFA as 5-tuples, the extended transition function and acceptance, complete versus partial DFAs and the dead state, why swapping final states complements a complete DFA but not an NFA or a partial DFA, the equal power of the three models, and Moore and Mealy machines with output lengths and conversions. Every automaton shown was simulated on all strings up to length 10.
A partial preview of the top of the sheet. The full sheet is in the Theory of Computation cheat sheet pack.
The subset construction from NFA or epsilon-NFA to DFA built on reachable subsets only, the empty set as the dead state, the 2^n upper bound and the k-th-symbol-from-the-end family that reaches it, the product construction for intersection, union, difference and symmetric difference with its m times n bound, examples where the product is not minimal, and the reversal blow-up. All subsets and state counts were computed by script.
A partial preview of the top of the sheet. The full sheet is in the Theory of Computation cheat sheet pack.
Minimising a DFA: remove unreachable states, refine the final and non-final partition until stable (Moore), or mark distinguishable pairs round by round (table filling), with a fully worked six-state example including an unreachable state; the Myhill-Nerode relation and why the minimal DFA is unique up to renaming; class counts for standard languages; algorithm costs; complement and equivalence facts; and counting labelled DFAs. Every partition, mark and count is script output.
A partial preview of the top of the sheet. The full sheet is in the Theory of Computation cheat sheet pack.
How to design DFAs by deciding what the machine must remember: remainder automata for divisibility in base 2 and other bases (with the m plus k rule for even divisors), substring, prefix and suffix automata, length and counting conditions, products of independent conditions, and counting the strings of length n that a DFA accepts by dynamic programming over states. Every minimal state count in the tables is computed by brute-force minimisation.
A partial preview of the top of the sheet. The full sheet is in the Theory of Computation cheat sheet pack.
