# Tag Archives: minimization # A Better Approach to DFA Minimization

DFA minimization is often described as follows:

1. First eliminate any unreachable states (easy).
2. 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.
1. Start by marking all pairs $$(p, q)$$ where $$p \in F$$ and $$q \not\in F$$, or vice versa.
2. 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)$$.
3. 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.

Continue reading