DFA minimization is often described as follows:
- First eliminate any unreachable states (easy).
- Then create a table of all possible pairs of states \((p, q)\), initially unmarked. (E.g. a two-dimensional array of booleans, initially set to false.) We mark pairs \((p, q)\) as and when we discover that \(p\) and \(q\) cannot be equivalent.
- Start by marking all pairs \((p, q)\) where \(p \in F\) and \(q \not\in F\), or vice versa.
- Look for unmarked pairs \((p, q)\) such that for some \(u \in \Sigma\), the pair \((δ(p, u), δ(q, u))\) is marked. Then mark \((p, q)\).
- Repeat step 2.2 until no such unmarked pairs remain. If \((p, q)\) is still unmarked, can collapse \(p\) and \(q\) to a single state.
Source: Mary Cryan, Informatics 2A: Processing Formal and Natural Languages, Lecture 5, 2018.
Based on my very limited research, aforementioned algorithm seems to be the most common way of teaching undergrads how to minimise a given DFA, but I believe that it suffers from reasons soon listed below, and I will instead propose a better way of executing the same algorithm that does not (make the student) suffer from the same problems.