Tag Archives: dfa

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