JOVANA
Explore Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

Same Power, Smaller Machine

You have met cloning, epsilon-moves, easy design, and the subset construction. Now the rung closes with the headline result: NFAs, epsilon-NFAs, and DFAs all recognize exactly the same languages. Nondeterminism never adds power — it only buys you a smaller, friendlier machine, and only as a mathematical device.

Four guides, one surprising conclusion

This rung gave you a richer machine in four moves. First you met nondeterminism as cloning: at a fork the machine splits into copies that each try a different branch, and the input is accepted if ANY clone reaches an accept state. Then you let a transition land in a whole SET of next states rather than exactly one, and added epsilon-moves that change state while reading nothing, with the epsilon-closure sweeping up every state reachable for free. Then you saw why this makes design easy. Finally, the subset construction turned any such machine back into an ordinary DFA. This guide ties all four together and states the punchline plainly.

Here is the conclusion, in one breath: every language an NFA can recognize, some DFA can recognize too; and every language an epsilon-NFA can recognize, some plain NFA (hence some DFA) can recognize too. The three machines are equivalent — fully interchangeable. Anything one of them accepts, the other two accept; anything one rejects, the other two reject. They are not three powers — they are one power wearing three costumes.

Why equivalence holds, in both directions

Equivalence is a two-way street, and one direction is almost free. A DFA is already an NFA — a particularly disciplined one whose every transition happens to land in a set of exactly one state, with no forks and no epsilon-moves. So nothing a DFA does is beyond an NFA; the only real work is the other direction, showing every NFA can be flattened down to a DFA. That harder direction is exactly the subset construction from the previous guide, and it is worth recalling the trick that makes it work.

  1. Track a SET, not a single state. The DFA you build has one state for each subset of the NFA's states. A DFA-state means 'the exact set of NFA-states the clones could be in right now.'
  2. Start from the epsilon-closure of the NFA's start state — every state reachable before reading anything. That set is the DFA's start state.
  3. To step on symbol a: from the current set, take every NFA-state's a-transitions, union all the targets, then take the epsilon-closure of the result. That single set is the next DFA-state.
  4. Mark a DFA-state as accepting if its set contains at least one of the NFA's accept states — that is exactly the 'some clone succeeded' rule.

Why does this make the result deterministic? Because a SET of NFA-states has exactly one successor set under each symbol — set-union and epsilon-closure are functions, they return one answer. The cloud of clones, taken as a whole, marches deterministically even though each clone was guessing. The accept rule mirrors NFA acceptance perfectly: a set counts as accepting iff at least one clone in it has succeeded. That is the whole proof of the hard direction, and together with the free direction it gives NFA-DFA equivalence. Fold in the fact that the epsilon-closure step already absorbs epsilon-moves, and you also get DFA equals NFA equals epsilon-NFA — the three models are equivalent, all recognizing exactly the regular languages.

Smaller, but with a worst-case price

If the machines are equivalent, why bother with NFAs at all? Because they are usually dramatically smaller and easier to design — that is NFA conciseness. When you want 'the input ends in abb,' an NFA can just guess that the abb starts here and verify, needing a handful of states; the equivalent DFA has to remember, at every position, how much of the pattern it has matched so far. An NFA lets you state WHAT you want and leave the bookkeeping to nondeterminism; a DFA forces you to do all the bookkeeping yourself.

But the subset construction hints at a cost. An NFA with n states has 2^n possible subsets, so the DFA it produces could in principle need up to 2^n states. Usually most subsets are unreachable and the real DFA is small, but for some carefully built languages the blowup genuinely bites: there are n-state NFAs whose smallest equivalent DFA truly requires about 2^n states. This is the exponential blowup, and it is not a weakness of the algorithm — it is a real, provable gap in size between the two representations.

Classic blowup family:  L_n = { strings whose n-th symbol from the END is 'a' }, over {a,b}

NFA  (n+1 states):  guess WHEN the n-th-from-end position arrives, then check n-1 more symbols.

  ->(q0) --a,b--> (q0)            stay, still scanning
     (q0) ---a---> (q1)           GUESS: 'this a is the n-th from the end'
     (q1) --a,b--> (q2) ... (qn)  verify exactly n-1 more symbols follow
     (qn) = accept

DFA:  must remember the LAST n symbols seen (cannot guess) ->  needs 2^n states.

  small, lazy NFA   (n+1 states)
  vs
  big, bookkeeping DFA   (2^n states)   <- the blowup is provably unavoidable here
The n-th-symbol-from-the-end language: an (n+1)-state NFA, but every equivalent DFA needs about 2^n states.

The lasting lesson: nondeterminism is a device

Now the deepest takeaway of the whole rung, the one to carry up the rest of the ladder. Nondeterminism is a mathematical convenience — not a more powerful kind of machine and not a piece of hardware. It is not randomness: a nondeterministic machine does not flip a coin and hope. The acceptance rule is the careful statement 'accept if SOME path leads to acceptance' — a claim about the existence of a good path among all possible paths, evaluated as if by a perfect oracle that always guesses right when a right guess exists. No physical machine 'tries all paths for free'; to actually run an NFA you simulate it, and the honest way to do that is the subset construction, which may cost those 2^n states.

So why keep nondeterminism around if it adds no power and is not real hardware? Because it is a superb design and proof tool. It separates the two halves of a problem cleanly: GUESS the part you do not yet know (where the abb begins, which factor to try), then deterministically VERIFY the guess. Designing the guesser is easy; the subset construction then does the tedious work of making it deterministic for you. This guess-then-verify pattern is not a finite-automata curiosity — it is the very heartbeat of one of the biggest ideas waiting far up this ladder: the class NP, where a problem is hard to solve but easy to verify once someone hands you a guessed certificate. The cloning machine you built here is your first, gentlest encounter with that idea.

What you can now do, and where it points

Step back and count what this rung bought you. You can now design a machine the lazy, expressive way — guessing and cloning, leaving epsilon-moves and the subset construction to clean up — and you know, with proof, that the convenient machine and the strict deterministic one accept exactly the same languages. You also know to expect a possible exponential blowup when you flatten an NFA, and you know NOT to mistake nondeterminism for power, randomness, or hardware.

Crucially, the boundary from the DFA rung did not move. NFAs, epsilon-NFAs, and DFAs all recognize precisely the regular languages — and remember that 'regular' does not mean 'finite' (the infinite language Sigma-star and a* are both regular). The wall built by the finite-memory limit still stands: a^n b^n remains unrecognizable by any of these three, because none of them can count without bound. The next rungs respond to that wall in two ways: regular EXPRESSIONS give you an algebra for exactly these languages, and pumping-style arguments let you prove a language sits outside them. The cloning trick you mastered here will keep paying dividends, all the way up to NP.