DFA vs NFA: What's the Difference?

A nondeterministic finite automaton (NFA) relaxes two rules a DFA enforces: a state can have zero, one, or several transitions on the same symbol, and transitions can also fire on ε (the empty string), consuming no input at all. An NFA accepts a string if at least one of the possible paths through the machine ends in an accept state after the whole string is consumed — not every path has to.

The same language, two machines

Both machines below decide the language "contains the substring 01 somewhere" over the alphabet {0, 1}.

DFA

The deterministic version has to track, precisely, how close the input is to containing 01: nothing seen yet (q0), a 0 just seen with no following 1 yet (q1), or 01 already found — an absorbing accept state, since once the substring appears the rest of the input can't undo it (q2).

q0⊢q1⊢q2⊢∈ F

NFA

The nondeterministic version instead "guesses" where the matching 01 starts. From p0 it can either stay put and keep scanning (self-loop on both symbols) or, on a 0, branch to p1 as a bet that this is the start of the match. If that bet was right, the next symbol being 1 lands the machine in the accepting p2. If the guess was wrong, that particular path dies — but the self-loop path is always still running in parallel, ready to guess again at the next 0.

Why they're equivalent anyway

Every NFA can be converted into an equivalent DFA via the subset construction: instead of tracking one current state, the DFA tracks the set of all states the NFA could be in after that many symbols. That set is always well defined, so a DFA can simulate an NFA exactly — it just might need exponentially more states to do it, and in practice usually needs far fewer.

Your turn