Determinization: Converting εNFA to DFA

mgcadmin 10-03-2026

Kleenes Theorem tells us of the equivelance between regular expressions and Finite Automata. It also informs us that any regular expression represented by an NFA can also be described by a DFA. Two other algorithms I have covered on this page also exploit this property: The NFA simulation using powerset construction as originally described by Thompson, and the Aho, Sethi, Ullman Direct-to-DFA construction.

In todays post I'm going to introduce a third application, though one which is intricantly linked to the other two by more than just a shared conceptual basis. We're going to cover the determinization of NFA, or how to convert an ε-NFA to a DFA using our by-now familiar friend, the powerset construction.

Regular Expressions To Finite Automata as a Pipeline

Just like any compiler, the process of converting a regular expression to a finite automaton can me modeled as a series of steps whos output serves as the input for the next step until we reach our desired output, in essence, a pipeline.

Thompsons Construction:
Regular Expression -> AST -> ε-NFA

Direct Method:
Regular Expression -> AST -> Followpos table -> powerset construction  -> DFA

Whether we are using Thompsons Construction or the direct method, the process of converting a regular expression string into a finite automaton takes place in a series of steps. While the direct method always leaves us with a DFA, Thompsons construction need not be brought all the way to a DFA, as we've already seen how to use the NFA directly for pattern matchning. There are times when a DFA is prefereable over an NFA, or even downright required. 

Thompsons Construction:
Regular Expression -> AST -> ε-NFA -> powerset construction -> DFA

Direct Method:
Regular Expression -> AST -> Followpos table -> powerset construction -> DFA

Interestingly, if we want to convert the NFA emitted by thompsons construction into a DFA, the last step of our new pipeline looks remarkably similar to that of the direct method, and thats no accident: The followpos table of the direct to dfa approach IS an NFA, just one without epsilon transitions!

From Sets of States to Single States with ε-Closure

struct DFAState {
    int label;
    bool accepts;
    set<NFAState*> positions;
    map<char, DFAState*> trans;
    DFAState(int l, set<NFAState*>& p) : label(l), positions(p), accepts(false) { }
};

The driving idea behind making an NFA deterministic is the conversion of sets of NFA states into singular DFA states. This is done by taking the lexical closure  or the expression. Any state which is reachable from the current state by following one or more epsilon transitions are added to the current set.

set<NFAState*> e_closure(set<NFAState*> states) {
    set<NFAState*> next = states;
    Stack<NFAState*> st;
    for (auto s : states) {
        st.push(s);
    }
    while (!st.empty()) {
        NFAState* curr = st.pop();
        for (auto t : curr->transitions) {
            if (t.is_epsilon && next.find(t.dest) == next.end()) {
                next.insert(t.dest);
                st.push(t.dest);
            }
        }
    }
    return next;
}

This is the same algorithm used in the non-backtracking NFA pattern matching algorithm, which coincidentally, is sometimes called the "on-the-fly DFA" method. Fancy that.

Gathering the Alphabet

In order to make our NFA deterministic we are going to need some helpers, and a bit of additional information. First of all, we will need to know the alphabet for the language our automaton automaton accepts. This is easy enough to obtain, we simply scan the provided expression making note of each unique character. If we encounter a wildcard symbol, we simply include the entire printable ascii range.

set<char> buildAlphabet(string expr) {
    set<char> aleph;
    for (int i = 0; i < expr.size(); i++) {
        char c = expr[i];
        if (isalpha(c) && !aleph.count(c)) { 
            aleph.insert(c);
        } else if (c == '.' && (i == 0 || expr[i-1] == '\\')) {
            for (int i = 20; i < 128; i++)
                aleph.insert((char)i);
        } // and so on for character classes
    }
    return aleph;
}

The only "gotcha" is if we encounter a wildcard symbol or character class. For character classes we add the range or set they signify, and for wildcards we simply include the entire printable ascii range.

Distinguishing DFAStates

Next, we'll need a way of identifying DFAStates to avoid creating duplicated states, which would be no bueno. We do this by comparing each states associated set of NFAStates. If two DFAStates have sets that are _exactly_ the same, the DFAStates are equal to each other and one can be discarded.

DFAState* findStateByPosition(DFA& dfa, set<NFAState*>& next) {
    for (int i = 0; i < dfa.num_states; i++) {
        if (equal(next.begin(), next.end(), dfa.states[i]->positions.begin(), 
            dfa.states[i]->positions.end(), [](NFAState* a, NFAState* b) { return a->label == b->label; })) {
            return dfa.states[i];
        }
    }
    return nullptr;
}

You have to becareful to check the entire sets: One state having a set of positions which is a subset of the other does not make them equal: the sets must be identical in both size and contents.

From NFA to DFA

With our alphabet in hand and the ability to distinguish DFAStates, we're ready to make our NFA deterministic. We begin by creating the initial state of the DFA. The initial state has the set of NFAStates produced by taking the epsilon closure of the input NFA's start state. Once our initial state is created we push it on to a queue which will serve as our work list, and commence with finding the other states of our DFA and the transitions between them.

DFA makeDeterministic(NFA& nfa, string expr) {
    set<char> aleph = buildAlphabet(expr);
    DFA dfa;
    set<NFAState*> ss;
    queue<DFAState*> fq;
    ss.insert(nfa.start);
    ss = e_closure(ss);
    DFAState* s = new DFAState(dfa.num_states++, ss);
    dfa.states[s->label] = s;
    fq.push(s);
    

We use the alphabet we gathered earlier to check each DFA State that we remove from the work list for any transitions from that state on that character. If there is a transition, we can check to see if its to a state we have already encountered and created, or if its to a state which we have yet to see and thus need to create.

    while (!fq.empty()) {
        DFAState* curr = fq.front(); fq.pop();
        for (char c : aleph) {
            set<NFAState*> next = move(c, curr->positions);
            if (!next.empty()) {
                next = e_closure(next);
                DFAState* p = findStateByPosition(dfa, next);
                if (p == nullptr) {
                    DFAState* n = new DFAState(dfa.num_states++, next);
                    curr->trans[c] = n;
                    fq.push(n);
                    dfa.states[n->label] = n;
                } else {
                    curr->trans[c] = p;
                } 
            }
        }
    }

This process continues until there are no more new states discovered, at which point the work queue is empty and the loop terminates. Finally, we scan the newly created states to see if any of their position sets contains our input NFA's accepting state, and if it does, we mark that state as our DFA's accepting state.

for (int i = 0; i < dfa.num_states; i++) {
        if (dfa.states[i]->positions.find(nfa.accept) != dfa.states[i]->positions.end()) {
            dfa.states[i]->accepts = true;
        }
    }
    return dfa;
}

And with that, we have converted our NFA to a DFA. But... is it really worth all that work? I mean, the NFA could have matched our pattern too right? Sure it could have, but our DFA does it as fast as possible, check out the DFA interpretartion loop for yourself:

bool matchDFA(DFA& dfa, string expr) {
    DFAState *next = nullptr, * state = dfa.states[0];
    for (int i = 0; i < expr.size(); i++) {
        if (state->trans.find(expr[i]) != state->trans.end()) {
            next = state->trans[expr[i]];
        }
        if (next == nullptr) {
            return false;
        } else if (next->accepts) {
            return true;
        } else {
            state = next;
            next = nullptr;
        }
    }
    return state != nullptr && state->accepts;
}

Happy Hacking!

---