Nondeterminism: Guessing and Cloning

Where the last rung left a gap

On the previous rung you built and ran a deterministic finite automaton — a controller like a turnstile that remembers nothing but its current state and, on each input symbol, follows exactly one rule delta(q, a) = p (in state q, reading symbol a, move to state p). The word that defines it is determinism: from any state, each symbol points at one and only one next state, so the machine's whole run is a single, fully forced path. You also met its hard limit — a finite memory cannot count without bound, which is why a^n b^n lies outside the regular languages.

Determinism is wonderfully predictable, but it can make designing a machine painful. Suppose you want to accept exactly the strings over the alphabet Sigma = {a, b} that end in the pattern a b b. A human reading left to right keeps wondering: 'is this the a that begins the final a b b, or just some a in the middle?' A DFA cannot wonder — it must decide, right now, with no peeking ahead. This rung introduces a machine that is allowed to wonder, by splitting itself and exploring several futures in parallel.

Guessing and cloning: the core idea

A nondeterministic finite automaton, or NFA, looks almost like a DFA, but its transition rule is relaxed in one bold way: from a state, on a given symbol, it may point to zero, one, or many next states. So instead of delta(q, a) = p (a single state), the rule becomes a transition into a set of states: delta(q, a) = {p1, p2, ...}, possibly the empty set. The picture to keep in your head is cloning. Whenever the machine faces several choices, imagine it splitting into one clone per choice, and every clone continues reading the rest of the input independently.

This raises the obvious question: with many clones running, who decides whether the machine accepts? The rule, NFA acceptance, is gloriously optimistic: the NFA accepts a string if at least one clone ends in an accept state. Equivalently, accept the string if some path of choices, read off symbol by symbol, lands on an accept state. If every clone dies (runs into the empty set of next states) or ends in a non-accept state, only then is the string rejected. A single successful path is enough to win.

A tiny example: strings ending in a b b

Watch how cloning dissolves the designer's headache. We want all strings over {a, b} ending in a b b. Build a four-state NFA with states q0, q1, q2, q3, start state q0, and only q3 accepting. Out of q0 we put TWO transitions on a: one self-loop a back to q0 (this clone says 'I am still skipping junk in the middle') and one a to q1 (this clone guesses 'the final a b b starts right here'). The rest just verifies the guess: q1 on b goes to q2, and q2 on b goes to q3. On every other symbol a guessing clone simply has no move and dies.

NFA for "ends in a b b"   (start = q0, accept = q3)

  state |   on a        |   on b
  ------+---------------+-----------
   q0   | {q0, q1}      | {q0}
   q1   | { }           | {q2}
   q2   | { }           | {q3}
   q3   | { }           | { }

Run on input  a b a b b   (track the SET of live clones):

  start         : {q0}
  read a        : {q0, q1}        (q0 stayed, and guessed -> q1)
  read b        : {q0, q2}        (q1 -> q2 ; q0 looped ; guess q1 had no... wait)
  read a        : {q0, q1}        (q2 had no 'a' move and died; q0 stayed+guessed)
  read b        : {q0, q2}        (q1 -> q2 ; q0 loops)
  read b        : {q0, q3}        (q2 -> q3 ; q0 loops)

  q3 is in the final set  ==>  ACCEPT  (some clone reached q3)

The NFA tries every starting point for the final a b b at once; we accept because one clone lands on q3 exactly as the input ends.

Two honest notes about that trace. First, when state q2 reads an a it finds the empty set as its target, so that particular clone simply vanishes — no error, no crash, it just stops being a live path; this is how the NFA quietly abandons wrong guesses. Second, you do not really run infinitely many clones; the practical way to simulate an NFA is to track, at each step, the set of states that some live clone could currently occupy. That set view of exploring all paths in parallel is exactly the seed of the conversion we meet at the end.

Why nondeterminism is not cheating

It feels like cheating: the machine seems to magically 'know' where the final a b b begins. But there is no oracle and no luck involved. The clean way to read an NFA is guess-and-verify: imagine the machine GUESSES a choice at every fork (here, where the final pattern starts), then deterministically VERIFIES that guess by reading on. The acceptance rule simply says the string is in the language if some guess could have been verified. Nothing is computed by chance; we are quantifying over all possible guesses with the word 'there exists.'

There is one more piece of NFA flexibility we will only name here and unpack in the next guide: a transition that consumes no input symbol at all, written on the empty string epsilon (the Greek letter ε). Such an epsilon-transition lets a clone drift to another state 'for free,' which makes it effortless to glue smaller machines together. For now just know it exists; the epsilon-closure that tames it is the very next topic.

Same power, smaller machine — and a warning

Here is the result that makes this whole rung beautiful, and a little surprising: nondeterminism buys you no extra recognizing power. NFAs, epsilon-NFAs, and DFAs all recognize exactly the same class of languages — the regular languages. This is the theorem NFA-DFA equivalence. So an NFA can never recognize a^n b^n either; nondeterminism only buys conciseness and ease of design, not reach. The convincing direction (every DFA is trivially already an NFA) is easy; the striking direction is that every NFA can be flattened back into some DFA.

The trick that flattens an NFA into a DFA is the subset construction (also called the powerset construction), and you already saw its heartbeat in the trace above. Since simulating an NFA means tracking the set of states some live clone could be in, just make each such set a single state of a brand-new DFA. We will run the full procedure on its own rung, but the four-move skeleton is short enough to taste right now.

The DFA's start state is the SET containing just the NFA's start state (later widened by epsilon-moves).
For a current set S and a symbol a, the next DFA state is the UNION of delta(q, a) over every q in S — exactly 'where could any live clone go on a.'
Keep generating new reachable sets until no new set appears; this must end because there are only finitely many subsets.
A DFA state (a set) is accepting exactly when it contains at least one of the NFA's accept states — mirroring 'accept if some clone is in an accept state.'

And here is the honest catch you should carry forward. An NFA with n states has 2^n possible subsets, so the resulting DFA can in the worst case have up to 2^n states — the dreaded exponential blowup. It is not just a theoretical fear: there are real languages whose smallest NFA has about n states while every DFA needs roughly 2^n. So the two models are equal in power but can be wildly unequal in size, and that trade-off — design with the small, easy NFA, then pay (sometimes dearly) to determinize — is the practical lesson this rung leaves you with.