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.
Regular expressions and finite automata define the same class of languages. One direction builds an ε-NFA from an expression (Thompson's construction). The other eliminates states from a DFA (or NFA) until a single regular expression remains.
A deterministic finite automaton (DFA) is a finite-state machine that reads an input string from left to right, one symbol at a time, and either accepts or rejects. At every step the next state is uniquely determined by the current state and the current symbol.
A nondeterministic finite automaton (NFA) may have zero, one or many next states for a given state and symbol. It accepts a string if some sequence of choices leads to an accepting state. Allowing ε-transitions (moves without reading input) gives an ε-NFA.
Two states of a DFA are equivalent when no string leads from one to an accept state and from the other to a reject state. Merging equivalent states yields the unique (up to renaming) minimal DFA for the language: fewest states among all DFAs for that language.
One-page visual sheets for this topic, in the sheet library on the store. Previews are free; the full sheets come with the subject pack.
