Every NFA has an equivalent DFA: a machine that accepts exactly the same language, but with a totally deterministic transition function. The algorithm that builds it is called subset construction (or the powerset construction), and the core idea is simple: instead of tracking a single active state, the DFA tracks the set of all NFA states that could be active after reading the input so far.

The Algorithm

Compute the ε closure of a state set: every state reachable using only ε transitions.
The DFA's start state is the ε closure of the NFA's start state.
For each DFA state (a set of NFA states) S and each input symbol a, the next DFA state is the ε closure of the union of δ(s, a) for every s in S.
A DFA state is accepting if the set it represents contains at least one NFA accepting state.
Repeat until no new state sets appear.

Worked Example

Take an NFA over {a, b} for "contains the substring ab": q0 is the start state, q2 is accepting.

q0 on a → {q0, q1}
q0 on b → {q0}
q1 on b → {q2}
q2 on a or b → {q2}

There are no ε transitions here, so ε closure of a set is just the set itself. Running subset construction from {q0}:

{q0}: a → {q0, q1}, b → {q0}
{q0, q1}: a → {q0, q1}, b → {q0, q2}
{q0, q2}: a → {q0, q1, q2}, b → {q0, q2}
{q0, q1, q2}: a → {q0, q1, q2}, b → {q0, q2}

No new sets appear after that, so the construction terminates with four DFA states. Any set containing q2, here {q0, q2} and {q0, q1, q2}, becomes an accepting DFA state.

Why It Can Blow Up

In the worst case an NFA with n states produces a DFA with 2ⁿ states, because every subset of NFA states is a candidate DFA state. In practice, as in the example above, most subsets are never reached from the start state, so the real machine is usually far smaller than the theoretical bound.

Try It Yourself

Build the NFA on the canvas, run "Convert NFA to DFA" from the menu, and compare the transition tables side by side. It's the same table shown above, generated automatically.