Equivalence of DFA and NDFA

Theory of Computation & Computer Graphics — Introduction to Finite Automata, NEC licence examination syllabus (Nepal Engineering Council).

Equivalence of DFA and NDFA

Non-determinism is a convenience, not a capability — and the subset construction is the proof.

🌍 Where this lives: This equivalence is what makes regular expression engines practical. A regex is naturally converted to an NFA — small, easy to build, with ε-transitions for alternation and repetition — but an NFA must explore many paths at once, which is slow. The subset construction converts it to a DFA that examines each input character exactly once with no backtracking, giving guaranteed linear-time matching. Tools like grep and lex do exactly this, which is why they never suffer the catastrophic backtracking that afflicts some backtracking regex libraries. Search "Thompson construction subset construction regex DFA linear time".

The theorem and the construction

THE THEOREM: FOR EVERY NON-DETERMINISTIC FINITE AUTOMATON N THERE EXISTS A DETERMINISTIC FINITE AUTOMATON D SUCH THAT L(D) = L(N). ONE DIRECTION IS TRIVIAL: every DFA IS an NFA — one whose transition function happens to return a singleton set every time. So DFA ⊆ NFA immediately. THE CONTENT OF THE THEOREM IS THE OTHER DIRECTION, and the proof is a construction. ── THE IDEA ──────────────────────────────────────────────── An NFA, given an input, may be in any one of several states. The DFA is built to TRACK THE ENTIRE SET OF STATES THE NFA COULD CURRENTLY BE IN. ONE DFA STATE = ONE SET OF NFA STATES. Because "the set of possible NFA states" is completely determined by the input read so far, THIS SET IS ITSELF A DETERMINISTIC FUNCTION OF THE INPUT — which is exactly what a DFA needs. ── THE SUBSET CONSTRUCTION (POWERSET CONSTRUCTION) ───────── Given N = (Q, Σ, δ, q₀, F), construct D = (Q′, Σ, δ′, q₀′, F′): Q′ = P(Q), the POWER SET of Q — every subset of NFA states is a potential DFA state q₀′ = ε-CLOSURE({q₀}) δ′(S, a) = ε-CLOSURE( ⋃_{q ∈ S} δ(q, a) ) — from the set S, on symbol a, take the union of everywhere each member could go, then close under ε-transitions F′ = { S ⊆ Q : S ∩ F ≠ ∅ } — a DFA state accepts if ANY NFA state in it accepts, because the NFA accepts if ANY path accepts THE ε-CLOSURE of a set S is S together with every state reachable from S by ε-transitions alone, applied repeatedly until nothing new is added. IN PRACTICE ONE DOES NOT BUILD ALL 2ⁿ SUBSETS. Start from the initial subset and generate only the subsets actually REACHABLE, which is usually a small fraction. ── A FULLY WORKED CONVERSION ─────────────────────────────── NFA accepting strings over {a,b} that END IN "ab": states 0, 1, 2 with 2 accepting; start 0 δ(0,a) = {0,1} (guess: this a begins the "ab") δ(0,b) = {0} δ(1,b) = {2} (all other transitions empty) THE NON-DETERMINISM IS THE GUESS at state 0: on reading a, the machine both stays (this was not the final ab) and moves to 1 (this was). It explores both. SUBSET CONSTRUCTION, starting from {0}: A = {0} on a: δ(0,a) = {0,1} → new state B on b: δ(0,b) = {0} → A B = {0,1} on a: δ(0,a) ∪ δ(1,a) = {0,1} ∪ ∅ = {0,1} → B on b: δ(0,b) ∪ δ(1,b) = {0} ∪ {2} = {0,2} → new state C C = {0,2} on a: {0,1} → B on b: {0} → A ACCEPTING STATES: C = {0,2} contains 2, so C accepts. A and B do not. THE RESULTING DFA: STATE a b ACCEPTING? ────────────────────────────────── →A {0} B A no B {0,1} B C no C {0,2} B A YES ────────────────────────────────── THREE STATES, from a possible 2³ = 8 SUBSETS. Only three were reachable, which is typical. SANITY CHECK: on input "aab" the DFA goes A →a B →a B →b C, ending in the accepting state C. On "aba" it goes A →a B →b C →a B, ending in B, correctly rejecting.

The state explosion, and what it means

── THE COST OF DETERMINISATION ───────────────────────────── AN NFA WITH n STATES CAN REQUIRE UP TO 2ⁿ STATES AS A DFA. This bound is TIGHT — it is not merely a worst case of a sloppy construction. THE CLASSIC WITNESS is the language L = { strings over {a,b} whose n-th symbol FROM THE END is an a } AN NFA NEEDS ONLY n+1 STATES: it non-deterministically guesses which a is the n-th from the end and then verifies that exactly n−1 symbols follow. ANY DFA NEEDS AT LEAST 2ⁿ STATES, and the reason is informative: a deterministic machine cannot guess, so it must REMEMBER THE LAST n SYMBOLS READ in order to know, when the string ends, what the n-th from the end was. There are 2ⁿ possible n-symbol windows and each must be a distinct state. THAT IS THE PRECISE SENSE IN WHICH NON-DETERMINISM IS A CONVENIENCE: IT REPLACES REMEMBERING WITH GUESSING. The DFA pays in states what the NFA saves by guessing. IN PRACTICE the blow-up is rare. Most NFAs arising from regular expressions yield DFAs of comparable size, which is why the conversion is used routinely despite the exponential worst case. ── THE ENGINEERING TRADE-OFF ─────────────────────────────── NFA DFA ──────────────────────────────────────────────────────── construction SMALL and easy may be exponentially size from a regex larger simulation time per symbol O(number of O(1) — one table active states) lookup total matching O(m · n) for text O(n) — LINEAR, time of length n guaranteed space small possibly large table building it immediate requires the subset construction first ──────────────────────────────────────────────────────── THE STANDARD RESOLUTION IN REAL TOOLS: build the NFA from the regular expression, then convert to a DFA either fully (for a pattern used many times, such as a compiler's lexer) or LAZILY — constructing DFA states on demand and caching them, so that only the subsets actually encountered are ever built. Lazy determinisation gets DFA speed without paying the full exponential cost up front. ── WHY THE RESULT MATTERS THEORETICALLY ──────────────────── Beyond the practical use, the equivalence tells us something about the CLASS of regular languages: 1. IT CONFIRMS THE CLASS IS ROBUST. Adding non-determinism — a substantial-looking change to the model — does not change what can be recognised. A definition that survives such a change is describing something real, not an artefact of one formalisation. The same class is reached by DFAs, NFAs, ε-NFAs, regular expressions and regular grammars. 2. IT LICENSES FREE MOVEMENT BETWEEN MODELS. In a proof one may use whichever is convenient — typically an NFA for constructions (union, concatenation, Kleene star are all trivial with non-determinism) and a DFA when a unique next state is needed (complement, minimisation). COMPLEMENT IS THE STANDARD ILLUSTRATION: to complement a DFA, swap accepting and non-accepting states, and that is all. DOING THE SAME TO AN NFA IS WRONG, because a string may have both an accepting and a rejecting path. 3. IT ESTABLISHES CLOSURE PROPERTIES cleanly, since each operation can be proved in whichever model makes it easiest. NOTE THE CONTRAST WITH LATER MODELS, which is worth carrying forward through this section: · FOR FINITE AUTOMATA, non-determinism adds NO power. · FOR PUSHDOWN AUTOMATA, non-determinism DOES add power — non-deterministic PDAs recognise all context-free languages while deterministic ones recognise only a proper subset. · FOR TURING MACHINES, non-determinism again adds no power (though the time cost is the open P versus NP question). SO "DOES NON-DETERMINISM HELP?" HAS A DIFFERENT ANSWER AT EACH LEVEL OF THE HIERARCHY, and that is a genuinely surprising fact about computation.

Non-determinism replaces remembering with guessing. The NFA for "the n-th symbol from the end is a" needs n+1 states because it can guess; any DFA needs 2ⁿ because it must instead remember the last n symbols. That is the exact sense in which non-determinism buys convenience rather than capability.

🌍 Go further: The choice between NFA simulation and DFA conversion has real security consequences. Backtracking regex engines — used in many programming language standard libraries — simulate the NFA by trying paths one at a time and undoing them on failure, which can take exponential time on inputs crafted to maximise backtracking. This is the basis of ReDoS, a denial-of-service attack where a short malicious string against a vulnerable pattern hangs a server. Engines built on the subset construction, like RE2 and the classic Unix tools, cannot be attacked this way because their matching time is linear by construction regardless of the pattern. The theory in this topic is the difference between a robust matcher and an exploitable one. Search "ReDoS catastrophic backtracking RE2 linear time matching".

💡 Exam angle: state the theorem and note that DFA ⊆ NFA is trivial so the content is the converse. Give the subset construction formally — Q′ = P(Q), the δ′ formula with ε-closure, and F′ as those subsets meeting F. The near-certain question is to convert a given NFA to a DFA: build the reachable subsets systematically, show the transition table, mark accepting states, and note how many of the 2ⁿ subsets were reachable. Know that the 2ⁿ bound is tight and be able to explain the "n-th symbol from the end" witness. Mention the trade-off — NFAs are small and easy to build, DFAs simulate in constant time per symbol.

Syllabus points

NFA → DFA (subset / powerset construction)
ε-NFA and ε-closure

Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.