DFA Minimization: Moore's Algorithm

mgcadmin 10-12-2026

When it comes to pattern recognition (especially of regular expressions) the DFA can't beat. Truly, the ability of a DFA to confirm or reject a pattern in linear time (O(n)) is a highly desirable trait, even better than 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. That's because DFA's have another great property: For every DFA that accepts a language L, there is a minimum state DFA', which accepts L without changing it. And so if we have an algorithm for computing our DFA, how do we than calculate its equivelant minimum state DFA?

As it turns out theres a number of ways to go about doing this, with two popular methods for minimizing a DFA being Hopcrofts Algorithm and Moores Algorithm. In todays post i'm going to go over Moores algorithm. While not as efficient as Hopcrofts algorithm in the worst case, Moores Algorithm is a touch easier to understand and implement, and for the average case it still completes in O(n log n). But thats enough background, lets get to it.

Moores Algorithm & Partition Refinement

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.

I find it helpful to frame set partition refinement as the opposite of union-find because it illustrates (to me at least) what it is that is supposd to be happening. Don't get to hung up on it though as were not actually using a disjoint set data structure, just its abstract representation.

The Initial Partition

In order to begim refining our partitions, we need to make some initial partitions in the first place. You can't refine what you havent defined. A good choice for the initial partitioning is the accepting status of a state: accepting states go in one group, non-accepting in another group. The startegy for lexical analyzers is a bit different. Since they recognize multiple different patterns and must identify which pattern it is that they did match, the initial partitions are done according to which pattern id they return. In this case, there can be much more than 2 inital partitions.

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 Partition Refinement

With our first parition complete, we continue the partitioning until no more partitions can be created. After the initial grouping, we switch to a more fine grained distinguishing factor: We use the states transitions. If a transition on a character takes two states in the same group to different destination states, they are not equivelant states and should be placed in different groups.

    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. This is the essence of partition refinement. 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 partition refinement. 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.

Rebuilding the reduced DFA with 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.

DFA 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. That's why they're grouped! 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. The only thing left to do is test it:

Expression: "(a|b)*abbd"
AST: 
 @
  @
   @
    @
     *
      |
       a
       b
     a
    b
   b
  d

Original DFA: 
--------------
0: 1(a) 2(b) 
1: 1(a) 3(b) 
2: 1(a) 2(b) 
3: 1(a) 4(b) 
4: 1(a) 2(b) 5(d) 
5: (Accept)

Reduced DFA:
---------------- 
0: 4(a) 0(b) 
1: (Accept)
2: 4(a) 0(b) 1(d) 
3: 4(a) 2(b) 
4: 4(a) 3(b) 

And one more thing: Depending on which algorithm you use to produce your input DFA will effect how much reducing will be performed. A DFA that was produced from an NFA that was made deterministic will have a much more impressive reduction than a DFA created with the Direct-to-DFA method, and the reason for that is epsilon transitions. Anyway, i thought it was interesting. Happy Hacking!

---