the complement construction

If you have a machine that says YES to exactly the strings you want, how do you get a machine that says YES to all the OTHER strings? For a deterministic finite automaton the answer is delightfully simple: flip every light. Wherever the machine used to accept, make it reject; wherever it used to reject, make it accept. Everything else — the states, the transitions, the start state — stays exactly the same.

Precisely: take a DFA M for a language L over alphabet Σ (Sigma) and form M' by making its accept states the non-accept states and vice versa (the new accept set is Q minus F, where F was the old accept set). Then M' recognizes the complement of L, written L-bar or Σ* minus L: every string over Σ that M rejected. This works because a DFA is TOTAL and DETERMINISTIC — on any input it follows exactly one path to exactly one final state, which is either accepting or not. So 'M accepts w' and 'M' accepts w' are exact opposites, string by string.

Two cautions make this honest. First, the DFA must be COMPLETE: every state needs a transition on every symbol, otherwise a 'missing' transition silently rejects and flipping the labels gets the wrong answer — add a trap state first if needed. Second, this trick does NOT work by simply swapping accept states on an NFA: an NFA accepts if SOME path accepts, so flipping its labels does not give the complement. To complement an NFA you first convert it to a DFA (subset construction), then swap.