Why must a finite automaton be deterministic and total before you complement it by flipping its accepting states?

## What flipping is supposed to do Complementing a language means accepting exactly the strings the original rejects. For a **deterministic, total** finite automaton the construction is as cheap as it gets: keep the states, the alphabet, the transitions and the start state exactly as they are, and swap the accepting and non-accepting sets. The state count does not change at all. The justification is a single sentence, and an interviewer wants to hear it rather than the recipe: in a deterministic total machine every input string has **exactly one** run, and that run ends in **exactly one** state. Acceptance is therefore a yes/no function of that final state, so inverting the set of final states inverts the answer on every string. Both words in "deterministic total" are load-bearing, and each one fails differently. ## Failure one: the machine is partial A partial machine has states with no outgoing edge on some symbol. Such a machine rejects by *getting stuck*, not by ending in a non-accepting state. Flipping the accepting set does nothing for those strings: they still get stuck, and the flipped machine still rejects them — yet they belong in the complement, because the original rejected them. Concretely, take a machine over the symbols `a` and `b` that accepts only `a`, with no `b` edges anywhere. Its complement should accept `b`. Flip its accepting states and the copy still has no `b` edge, so it still rejects `b`. The flipped machine accepts a strict subset of the true complement. The repair is mechanical: 1. Add one fresh **trap state** with a self-loop on every symbol. 2. Route every missing transition to the trap. The machine now has exactly one edge per state per symbol and accepts the same language as before. 3. Flip. The trap, previously non-accepting, **becomes accepting** — which is right, because exactly the strings that drove the original into the trap are the ones it rejected. That last point catches people out: a candidate who adds the trap and then leaves it rejecting after the flip has reintroduced the original bug at one remove. ## Failure two: the machine is nondeterministic A nondeterministic machine accepts a string when **at least one** run ends in an accepting state. It rejects when **every** run fails. Flipping the accepting set changes what each run reports but leaves the existential quantifier alone, so the flipped machine accepts when *some* run ends outside the original accepting set. That is a different question, and the two can both say yes on the same string. Take a machine with a start state `s` and an accepting state `t`, where `s` has two edges on `a`: one back to `s` and one to `t`. It accepts any nonempty run of `a`s. Flip the accepting set so `s` accepts and `t` does not. On input `a` the runs end in `s` or in `t`; the run ending in `s` is accepting, so the flipped machine accepts `a` — and so did the original. A machine and its supposed complement agreeing on a string is proof the construction is wrong. The legal route is determinise first, complete the result, then flip. ## What it costs | what you have | complement recipe | state count | |---|---|---| | deterministic and total | flip the accepting set | unchanged | | deterministic, partial | add a trap, route missing edges, flip | one more than before | | nondeterministic | determinise, complete, flip | up to two to the power of the original count | The asymmetry is the reason the order of closure operations matters in practice. Intersection and union by pairing stay polynomial, so a pipeline that complements **once**, on the smallest operand, and pairs everything else is affordable; one that complements repeatedly on nondeterministic intermediates may not be. The blow-up is not merely an artefact of a lazy algorithm: families of machines are known for which any deterministic machine for the complement really does need exponentially many states. ## Why this matters away from the whiteboard Any rule engine that supports "everything except" is complementing something. If its rules compile to nondeterministic machines, the negation is the operation that can make build time explode, while the positive combinations stay cheap. Knowing which single step in a rule pipeline is the expensive one — and that it is negation, not conjunction — is the whole payoff of this material.