Why Are NFAs and DFAs Equivalent in Computing?

Non-deterministic finite automata and deterministic finite automata recognize the exact same class of languages, known as regular languages. Although non-determinism appears to give a machine extra computational power by allowing multiple transitions or guesses at once, any non-deterministic finite automaton can be systematically converted into an equivalent deterministic finite automaton. This equivalence holds because a deterministic machine can track the entire set of states the non-deterministic machine might be in at any given step.

Deterministic vs. Non-Deterministic Automata

A deterministic finite automaton (DFA) is formally defined as a 5-tuple \(M = (Q, \Sigma, \delta, q_0, F)\), where:

  • \(Q\) is a finite set of states
  • \(\Sigma\) is a finite input alphabet
  • \(\delta: Q \times \Sigma \to Q\) is the transition function
  • \(q_0 \in Q\) is the start state
  • \(F \subseteq Q\) is the set of accepting states

In a DFA, for every state and every input symbol, there is exactly one next state.

A non-deterministic finite automaton (NFA) is defined similarly as \(N = (Q, \Sigma, \delta_N, q_0, F)\), except its transition function is \(\delta_N: Q \times (\Sigma \cup \{\epsilon\}) \to \mathcal{P}(Q)\), where \(\mathcal{P}(Q)\) is the power set of \(Q\). This means an NFA can transition to zero, one, or multiple states on a single input symbol, and it can also make \(\epsilon\)-transitions without consuming any input.

An NFA accepts an input string \(w\) if there exists at least one valid path through its states that leads to an accepting state in \(F\).

The Subset Construction

Because every DFA is trivially an NFA (with single-element sets as transition outputs and no \(\epsilon\)-transitions), any language recognized by a DFA is also recognized by an NFA. The reverse direction—proving that every NFA can be simulated by a DFA—is established using the subset construction (or powerset construction).

The key insight is that while an NFA can be in multiple states simultaneously, the total number of possible subsets of states is finite. If the NFA has \(|Q| = n\) states, there are at most \(2^n\) subsets of \(Q\).

To construct an equivalent DFA \(D = (Q_D, \Sigma, \delta_D, q_{D0}, F_D)\) from an NFA \(N\):

  1. States: Each state in \(Q_D\) corresponds to a subset of \(Q\), so \(Q_D = \mathcal{P}(Q)\).
  2. Start State: The start state \(q_{D0}\) is the \(\epsilon\)-closure of \(\{q_0\}\), denoted \(E(\{q_0\})\), which is the set of all states reachable from \(q_0\) using zero or more \(\epsilon\)-transitions.
  3. Transitions: For any subset \(R \subseteq Q\) and input symbol \(a \in \Sigma\), the DFA transitions to the set of all states reachable from any state in \(R\) on input \(a\), followed by any number of \(\epsilon\)-transitions: \[\delta_D(R, a) = \bigcup_{r \in R} E(\delta_N(r, a))\]
  4. Accepting States: A state \(R \in Q_D\) is accepting if it contains at least one accepting state from the NFA: \[F_D = \{R \subseteq Q \mid R \cap F \neq \emptyset\}\]

Why Non-Determinism Adds No Extra Power

In classical computing, an NFA does not actually "guess" the right path magically; rather, its acceptance condition asks whether any path succeeds. By tracking the set of all reachable states at each step, the DFA simulates all possible computation paths of the NFA in parallel.

If a string \(w\) is accepted by the NFA, at least one path ends in an accepting state, meaning the subset tracked by the DFA at the end of \(w\) will contain that accepting state. Conversely, if the DFA ends in an accepting subset, there must be at least one valid path in the NFA that reaches an accepting state.

The Trade-Off: State Complexity

While NFAs and DFAs have identical language recognition power, they differ in conciseness. Converting an NFA with \(n\) states into a DFA can require up to \(2^n\) states in the worst case. Non-determinism therefore provides an exponential advantage in representational efficiency for certain languages, even though it does not expand the boundary of what can be recognized.