DFA Minimization: Moore's Algorithm

mgcadmin 10-12-2026

When it comes to pattern recognition (especially of regular expressions) the DFA is hard to beat. The ability of a DFA to confirm or reject a pattern in linear time (O(n)) is a highly desirable trait, much better than O(mn) required when using an NFA Directly. Unfortunately the same cannot be said for its space complexity. When making an NFA deterministic it is not unusual to encounter a scenario which results in "state explosion" where an automaton that was build using n NFA states requires 2^n DFA states.

One naturally might wonder then is there a DFA with equivelant language recognition power but which uses fewer states? As it turns out, quite often there is. Two popular methods for minimizing a DFA are known as Hopcrofts Algorithm and Moores Algorithm. In todays post i'm going to go over Moores algorithm. While not as efficient as Hopcrofts algorithm, Moores Algorithm is a touch easier to understand and implement. 

Moores Algorithm

Moores algorithm is based around the idea of set partition refinement. Set partition refinement(SPF) is an interesting process that makes use of disjoint sets. Unlike union-find which starts with singleton sets and merges them to find large components, SPF starts with large sets (often just 2) and repeatedly splits them into more fine-grained sets. In this way, SPF is very much the opposite of uninon find.

The Initial Partition

In order to being refining our partitions, we need to make some partitions in the first place. A good choice for the initial partitioning is the states accepting status: accepting states go in one group, non-accepting in another group.

vector<set<int>> initGroups(DFA& dfa, map<int,int>& in_group) {
    vector<set<int>> groups= {{}, {}};
    for (int i = 0; i < dfa.num_states; i++) {
        if (dfa.states[i]->accepts) {
            groups[1].insert(i);
            in_group[i] = 1;
        } else {
            groups[0].insert(i);
            in_group[i] = 0;
        }
    }
    return groups;
}

We also keep an index of which state was put into which group, this is will come in very handy when its time to re-do our transition tables.

Iterative Refinement

With our first parition complete, we continue the partitioning until no more partitions can be created. Since we already determined which groups can be distinguished by acceptance, we'll use a different distinguishing factor.

    map<int,int> in_group;
    vector<set<int>> groups = initGroups(dfa, in_group);
    bool didchange = false;
    do {
        didchange = false;
        for (set<int>& group : groups) {
            set<int> ng;
            auto it = group.begin();
            int first = *it++;
            int next = (it != group.end()) ? *it++:0;
            

 

           while (next != 0) {
                for (char c : alphabet) {
                    int gtf = -1, gtn = -1;
                    if (dfa.states[first]->trans.find(c) != dfa.states[first]->trans.end()) {
                        gtf = dfa.states[first]->trans[c]->label;
                    }
                    if (dfa.states[next]->trans.find(c) != dfa.states[next]->trans.end()) {
                        gtn = dfa.states[next]->trans[c]->label;
                    }
                    int first_group = in_group[gtf]; 
                    int next_group = in_group[gtn]; 
                    if (first_group != next_group) {
                        ng.insert(next);
                    }
                }
                next = it != group.end() ? *it:0;
                it++;
            }

If we do find distinguishing states in the current group, we place them in the new group. Once inserted in the new group, we remove those states placed in the new group from their old group. We also update the in_group mapping to point to the states new location. 

            if (!ng.empty()) {
                for (int s : ng) {
                    group.erase(s);
                    in_group[s] = groups.size();
                }
                groups.push_back(ng);
                didchange = true;
                break;
            } else {
                didchange = false;
            }
        }
    } while (didchange);

Finally, we update the did_change flag to indicate that we're going to need another round of set partitioning. Once we go through a set parititoning iteration without making a change to any of the groups, we're done with this phase of the minimization. The next phase is where the actual "shrinking" takes place.

Re-Mapped Transitions

The resultant DFA of our minimization will have an equal number of states to the number of groups we ended up with during our set partitioning. As such, we begin by initializing our new DFA and creating the new states. At first, all nodes are marked as non-accepting.

FA rebuildMinimal(DFA& dfa, vector<set<int>>& groups, set<char>& alphabet, map<int,int>& in_group) {
    DFA result;
    result.num_states = groups.size();
    for (int i = 0; i < result.num_states; i++) {
        result.states[i] = new DFAState();
        result.states[i]->label = i;
        result.states[i]->accepts = false;
    }

Next we loop over our newly created states and re-map our old transitions to their new states. A "representative" state from each group is chosen arbitrarily - the first one will do, as they all have the same transititions, remember? Any transitions are inserted into the new states transition table, being careful to update the destination to the new state number. 

     for (int i = 0; i < result.num_states; i++) {
        int rep = *groups[i].begin();
        for (char c : alphabet) {
            if (dfa.states[rep]->trans.count(c)) {
                int ndst = in_group[dfa.states[rep]->trans[c]->label];
                if (ndst != -1) {
                    cout<<"Add transition "<<i<<" -> "<<c<<" -> "<<ndst<<endl;
                    result.states[i]->trans[c] = result.states[ndst];
                }
            }
        }

Finally, we iterate over the current group being processed, and if any of it's collapsed states were accepting states, we mark the current state being created as accepting as well.

      for (int os : groups[i]) {
            if (dfa.states[os]->accepts) {
                result.states[i]->accepts = true;
                break;
            }
        }
    }
    freeDFA(&dfa);
    return result;
}

After cleaning up the memory of our now no-longer-needed input DFA we return our resulting minimized DFA.

---