The Machine That Guesses

Last week's machine was honest to a fault: one arrow per symbol per state, no choices, no luck. Tonight we hand the machine a superpower we know real computers do not have — and then, on Thursday, we take it away again and discover that nothing of value is lost. That round trip, there and back, is one of the prettiest results in this course, and you will implement it in Project 1.

Start with a language that sounds trivial: T = strings over {a, b} whose third symbol from the end is an a. Checking membership by eye is instant — look three from the right, done. Now try to be the conveyor-belt machine from Notes 02. You read left to right, and you do not know when the string ends. So you can never point at the decisive symbol as it goes by; any a you see might be the third-from-last, and you will not find out until two more symbols arrive and the belt stops. A DFA must therefore carry the last three symbols in its state at all times — a rolling window, 2³ = 8 states, arrows everywhere. It works, and it is joyless, and designing it by hand invites errors.

Here is the strategy you actually want, stated as a human would: skim the string; at some moment of your choosing, point at an a and declare "that one is third from the end"; then verify that exactly two more symbols follow. The declaration is a guess about the future. Determinism forbids it. Tonight's machine permits it.

Nondeterminism is not randomness. It is the license to be judged only on your best possible run.

A nondeterministic machine may have several arrows for the same symbol out of a state — or none. Faced with a choice, what does it "do"? There are three standard readings, all equivalent, and you should own all three, because different situations make different ones natural.

Reading one: the lucky guesser. The machine makes choices as it runs, and it is judged with maximal charity: the input is accepted if some sequence of choices leads to acceptance. Imagine an oracle whispering the right choice at each fork. If any whisper-sequence works, that is the machine's run. Rejection means something strong under this reading: no possible sequence of choices succeeds — even perfect luck loses.

Reading two: parallel worlds. The machine never chooses; it splits. At each fork, reality forks with it, and all alternatives run simultaneously, one world per alternative. A world with no arrow for the next symbol dies. The input is accepted if, when the string ends, at least one surviving world stands on an accepting state. This is the reading that becomes an algorithm — you can feel it wanting to be a set of states — and it drives both labs tonight.

Reading three: the certificate. Forget machinery: w is accepted exactly when there exists an accepting path through the diagram spelling out w. Nondeterminism is an existential quantifier wearing a machine costume. A claimed path is a certificate — easy to check, and the machine's job is merely to assert that one exists. Hold on to this reading; it returns with a vengeance in Week 13, where "there exists a certificate" has a famous name.

One reading is conspicuously absent: probability. An NFA does not flip coins, and we never ask "with what chance is w accepted?" — only "does at least one accepting path exist?" Yes or no, as always. The machine is a bookkeeping fiction for quantifying over paths, and Thursday we will compile the fiction away entirely.

One change to the five-tuple carries all three readings. In a DFA, δ hands back a state. In an NFA, δ hands back a set of states — any set, including the empty one — and it may also move on no symbol at all.

Read the differences off the type. δ(q, a) may have two members: a fork, two worlds. It may have one: an ordinary deterministic step. It may be empty: no arrow, and a world standing at q reading a simply dies. And the ε column lets structure move the machine spontaneously — we will see in a moment why that is worth having. A DFA is exactly the special case where every δ(q, a) is a singleton and every δ(q, ε) is empty, so every DFA is an NFA. The inclusion is free; the question with content runs the other way, and it is Thursday's business.

Here is the guessing strategy for a simpler cousin of T — strings ending in ab — written as an NFA. State 0 skims. At any a, the machine may (not must) guess "the final ab starts here" and move to state 1. State 1 demands a b and reaches state 2; state 2 demands the string end, which it enforces by having no arrows at all.

As a table, with cells now holding sets. This is where nondeterminism becomes visible at a glance: any cell with two or more states is a fork, any ∅ is a dying world, and any populated ε column is spontaneous motion.

Compare with a DFA table: there, every cell holds exactly one state. Here, cells hold subsets — the totality discipline is gone, and P(Q) has replaced Q.

Notice how lopsided this is. To show a string is accepted, exhibit one path. To show it is rejected, you must argue about every path — all guesses fail, all worlds die or end cold. Existence is cheap to demonstrate and universality is expensive, and that asymmetry will follow us for the rest of the term: it is why complementing an NFA is not the innocent operation it is for a DFA, and its heavyweight cousin is the P versus NP question itself.

The ε-transition needs one supporting definition before we can run machines honestly. If the machine may hop for free, then "where the machine is" always means "where it is, plus everywhere reachable by free hops."

A worked example that also shows why ε is worth having. Let N₃ decide, over Σ = {a}, whether the string's length is a multiple of 2 or of 3. Build a 2-cycle p₀ → p₁ → p₀ and a 3-cycle t₀ → t₁ → t₂ → t₀, accepting at p₀ and t₀ — then let a start state s hop into both cycles by ε: δ(s, ε) = {p₀, t₀}. The machine guesses, before reading anything, which divisibility it will be lucky about. The initial world-set is E({s}) = {s, p₀, t₀}: one string, three worlds, before a single symbol is read. Two independent machines glued by ε into their union — that gluing is exactly how regular-expression alternation compiles in Week 4.

Now watch all of it move. The tracker below runs the parallel-worlds reading: the chips are states, the lit chips are living worlds, and the log narrates each step — move on the symbol, then ε-close, then count the survivors. Start with N₁ on bab and predict the lit set before each step; then switch to N₂ on abaab and watch worlds fork and die; finish with N₃ on aaaa, and then aaaaa.

The deep reason NFAs are pleasant to design with: language specifications are full of the words somewhere, or, and some, and nondeterminism transcribes each one directly. Three idioms cover most designs you will ever write.

Idiom 1 · guess the occurrence: "contains abba"

Skim in state 0; at some a, guess that the abba starts here; then demand b, b, a in order; then skim forever in the accepting state. Five states in a row, loops at both ends, arrows spelling the target — you can read the substring straight off the diagram. δ(0,a) = {0,1}, δ(1,b) = {2}, δ(2,b) = {3}, δ(3,a) = {4}, and state 4 loops on everything, accepting. The deterministic version of this machine exists — Week 4's methods build it — but it must encode how partial progress overlaps with itself (after abb, an a is both a failure of one attempt and the start of another), which is precisely the bookkeeping the guess spares you.

Idiom 2 · guess the branch: unions for free

N₃ in §04 was the pattern: machines for two languages, glued by ε-transitions from a fresh start state. The result recognizes the union, always, with no analysis of how the two machines interact — they never do. You cannot glue two DFAs this cheaply; last week's product construction was the deterministic price of the same union. ε is structural glue, and gluing is why regular-expression operators compile so cleanly.

Idiom 3 · guess the moment: "third symbol from the end is a"

The language T from §01, at last. Skim in state 0; at some a, guess "third from the end"; then consume exactly two more symbols of any kind; accept only if the string ends on cue. Four states: δ(0,a) = {0,1}, δ(0,b) = {0}, δ(1,·) = {2}, δ(2,·) = {3}, state 3 arrowless and accepting. Four states against the DFA's eight — and for "tenth from the end," eleven states against the DFA's 2¹⁰ = 1,024. Write the spec, not the bookkeeping.

An NFA is how you write the language down. A DFA is how you run it. The subset construction is the compiler between them.

Now the compilation. Stare at the worlds tracker once more: at every moment, everything relevant about the NFA's past is captured by the set of living worlds. And the tracker updates that set with no guessing whatsoever — move each world on the symbol, union the results, ε-close. The update is a function. Deterministic. So the fiction dissolves into an engineering fact: a DFA whose states are sets of NFA states can do everything the NFA does.

P(Q) is finite — 2^|Q| members — so D is a legitimate DFA. But most subsets are usually junk that no input ever reaches. In practice, and in Project 1, you build lazily: start from S₀, compute where each symbol leads, and only ever process sets you have actually discovered. Here is the entire computation for N₁, "ends with ab":

Row 1. S₀ = E({0}) = {0} (no ε-arrows in N₁). On a: world 0 forks, ⋃ = {0, 1}. New set — put it in the queue. On b: {0}. Already known.
Row 2. Process {0, 1}. On a: 0 forks to {0, 1}; 1 has no a-arrow and contributes nothing; union {0, 1} — already known. On b: 0 gives {0}; 1 gives {2}; union {0, 2}. New — queue it.
Row 3. Process {0, 2}. On a: 0 forks, 2 is arrowless; {0, 1}. Known. On b: {0}. Known. Queue empty — done.

Three reachable subsets, out of 2³ = 8 possible. F′ = {{0,2}}, the one set containing NFA-state 2.

And look at what the machine turned out to be — the subsets mean something. {0} is "no progress toward a final ab"; {0, 1} is "the previous symbol was a"; {0, 2} is "the previous two symbols were ab." The construction re-derived, mechanically, exactly the states a careful human designer would have chosen. Here is the same table as a diagram:

Why is the construction correct? One invariant, proved with the Notes 01 toolkit — induction on the length of w: after reading w, D sits exactly on the set of states N could be in after reading w. The base case is the definition of S₀ (ε-hops before any input); the step is the definition of Δ (worlds move, union, ε-close). Acceptance then coincides on every string: D accepts iff its final set contains an NFA-accepting state iff some N-path accepts. That gives the theorem — for every NFA there is a DFA recognizing the same language — and the invariant, written out in your own words, is precisely the correctness argument Project 1 asks of you.

Two footnotes before you drive it yourself. If every world dies, the construction discovers the subset ∅, whose every arrow loops back to ∅: a rejecting trap, the graveyard of worlds, and a perfectly legitimate DFA state. And do not confuse "reachable" with "few": the lazy build only sometimes stays small, as the third machine below demonstrates the hard way.

The equivalence deserves a minute of appreciation before we price it. NFAs looked strictly stronger: guessing, forking, free moves. The theorem says the appearance was an illusion — the class of languages is identical. Anything specifiable with guesses is implementable without them. So "regular language" is a robust notion: DFA-definable and NFA-definable coincide, and Week 4 adds a third door to the same room, definable-by-regular-expression. When several unrelated definitions keep carving out the same class, you have found a natural kind, not an artifact of one machine's design.

It also means something practical and slightly wonderful: guessing is compilable. The subset construction is not an existence proof that sits in a book — it is an algorithm you will ship this month, and its output runs at DFA speed: one table lookup per input symbol, no search, no backtracking, no luck required.

Now the price. The compiled DFA has, in the worst case, 2ⁿ states for an n-state NFA — and the worst case is not rare bad luck; it is sitting in §05. Take L_k = "the k-th symbol from the end is a," with its lovely (k+1)-state NFA. Any DFA for L_k needs 2^k states, and the §07 argument from Notes 02 shows why: if two strings with different last-k windows reached the same state, the machine has forgotten a difference — append the right number of symbols to slide the disagreement into the k-th-from-the-end seat, and the machine answers one of the two strings wrongly. 2^k windows, so 2^k states, and no cleverness escapes it. (Week 5's Myhill–Nerode theorem turns this style of argument into a precise machine-counting tool.) The blowup is not a weakness of the algorithm; it is a fact about the languages.

Where this bites in the real world: regular-expression engines. One family (grep, RE2, and their relatives) compiles patterns toward DFAs — blazing per-character speed, but state explosion must be managed, capped, or built lazily on the fly. Another family (the backtracking engines in Python, JavaScript, Java) explores the NFA's worlds one at a time with retreat — usually fine, but hand a pattern like (a|a)*b a long run of a's with no b at the end, and the engine must fail its way through every one of the 2ⁿ ways to parse the run before giving up — matching takes centuries; that is "catastrophic backtracking," and it has taken down production services often enough to have a security name, ReDoS. The sane middle path is the one you built in the tracker: simulate the set of worlds directly, all at once — O(|Q|) work per symbol, no compilation, no explosion, no retreat. Three strategies, one theorem, different engineering trade-offs. §08 gives you the third one in twenty lines.

The representation extends Notes 02's dict shape in exactly the way δ's new type demands: cells hold sets of states, a missing entry means ∅, and the key "" — the empty string, fittingly — holds the ε-arrows. Here is N₁:

ENDS_AB = {
    "alphabet": {"a", "b"},
    "states":   {0, 1, 2},
    "start":    0,
    "accept":   {2},
    "delta": {
        0: {"a": {0, 1}, "b": {0}},
        1: {"b": {2}},
        2: {},
    },
}

First tool: ε-closure, as a graph walk — keep chasing free hops until nothing new appears. It returns a frozenset, the immutable set Python allows as a dictionary key; that choice is about to matter, because the converter uses world-sets as keys of its transition table.

def eclose(n, states):
    """Everything reachable from `states` by zero or more ε-moves."""
    seen, stack = set(states), list(states)
    while stack:
        q = stack.pop()
        for r in n["delta"].get(q, {}).get("", set()):
            if r not in seen:
                seen.add(r)
                stack.append(r)
    return frozenset(seen)

The simulator is the worlds tracker, verbatim: carry the set of living worlds, and per symbol do move–union–close. The early return on an empty set is not merely an optimization — it is the honest reading of §04: no worlds, no possible witness, no way back.

def run_nfa(n, w):
    """Decide membership by simulating all worlds at once."""
    current = eclose(n, {n["start"]})
    for ch in w:
        moved = set()
        for q in current:
            moved |= n["delta"].get(q, {}).get(ch, set())
        current = eclose(n, moved)
        if not current:              # every world died
            return False
    return bool(current & n["accept"])

And the converter — the algorithm of §06, with the lazy worklist. Compare it line for line with run_nfa: the same move–union–close core, but instead of following one input, it charts every reachable world-set once and records the map. Simulation explores one road; construction paves them all.

def nfa_to_dfa(n):
    """Subset construction. Builds only the reachable subsets."""
    start = eclose(n, {n["start"]})
    delta, work = {}, [start]
    while work:
        S = work.pop()
        if S in delta:
            continue                 # already processed
        delta[S] = {}
        for ch in sorted(n["alphabet"]):
            moved = set()
            for q in S:
                moved |= n["delta"].get(q, {}).get(ch, set())
            T = eclose(n, moved)
            delta[S][ch] = T
            work.append(T)
    return {
        "alphabet": n["alphabet"],
        "states":   set(delta),
        "start":    start,
        "accept":   {S for S in delta if S & n["accept"]},
        "delta":    delta,
    }

# ε first, always — then both verdicts, then the compiled machine
assert run_nfa(ENDS_AB, "") is False
assert run_nfa(ENDS_AB, "ab") is True
assert run_nfa(ENDS_AB, "ba") is False
D = nfa_to_dfa(ENDS_AB)
print(len(D["states"]))              # 3 — of 8 possible subsets

Note what the output is: a DFA in last week's dict shape, whose states happen to be frozensets — run_dfa from Notes 02 §08 can execute it unchanged. That composability is by design, and it is the spine of Project 1: parse a machine file, simulate DFAs, simulate NFAs, convert, and show both machines agree on a test suite. The written half of the project is the §06 invariant in your own words — you have now seen the proof, run the proof, and coded the proof; writing it is the easy quarter of the job.

Six questions. Answer before you click — being wrong here is free and useful.

Project 1 work begins now — the specification has been out for a week, and everything it asks for has now appeared in these notes. Week 4 closes the triangle with regular expressions, so arrive fluent in tonight's two algorithms.

Coming up

Sessions 6 and 7 (Sept 22, 24) — Notes 04. Regular expressions: the algebra of the regular languages, the compilation pipeline regex → NFA → DFA that completes tonight's picture, and the closure properties that let you argue about languages without building machines at all. Project 1 continues; the converter you met tonight is its centerpiece.

If any part of tonight did not land, email me — yair.chaya@liu.edu — or ask for an office-hours slot. Replies within 24 hours.