NFA-DFA Equivalence Theorem
You'll learn why nondeterministic and deterministic finite automata are fundamentally the same in power.
The Core Idea
Although NFAs seem more powerful because they can "guess" the right path and have epsilon transitions, they recognize exactly the same class of languages as DFAs: the regular languages.
This is surprising at first—NFAs feel more flexible. But the Subset Construction algorithm you just learned is the key: for any NFA, we can construct an equivalent DFA that accepts the same language. Since DFAs are a special case of NFAs (every DFA is technically an NFA with no epsilon transitions and exactly one transition per symbol), they form a perfect two-way equivalence.
The Theorem Statement
For every language L:
- L is recognized by some NFA if and only if L is recognized by some DFA.
Why It Matters
This means "nondeterminism is free" for recognition—it doesn't expand what languages you can recognize, only how conveniently you can describe them. An NFA might have 5 states where the equivalent DFA needs 20, but both recognize the same strings.
Since regular expressions, NFAs, and DFAs all define the same class (regular languages), you can freely choose the most convenient model for your task: regex for specification, NFA for construction, DFA for implementation.
Proof Sketch
- DFA → NFA: Trivial. Every DFA is already an NFA.
- NFA → DFA: Use the Subset Construction algorithm to convert any NFA into an equivalent DFA.
Key Takeaway: NFAs and DFAs are equivalent in power—both recognize exactly the regular languages, though NFAs may be exponentially more compact.