Complementing DFAs
What you'll learn: How to build a DFA that accepts the exact opposite set of strings by simply swapping which states are accepting.
The Core Idea
Imagine you have a DFA that accepts all strings containing an even number of 1s. Complementing this DFA means creating a new DFA that accepts everything else—strings with an odd number of 1s.
The beautiful part? You don't need to redesign anything from scratch. Since a DFA processes every string and always ends in exactly one state, complementing is trivial: just flip the accept/reject labels on all states.
How It Works
Given a DFA M = (Q, Σ, δ, q₀, F):
- Keep the same states (Q)
- Keep the same alphabet (Σ)
- Keep the same transition function (δ)
- Keep the same start state (q₀)
- Swap the accept states: F' = Q - F (all non-accepting states become accepting, all accepting states become non-accepting)
That's it! The complement DFA accepts exactly those strings that the original DFA rejected.
Why This Works
A DFA is complete—every state has a transition for every symbol, and every string leads to exactly one state. A string is either accepted (ends in F) or rejected (ends in Q - F). By swapping these sets, you capture precisely the opposite language.
Think of it like a switch: if the original DFA says "yes" to a string, the complement says "no," and vice versa. No string falls through the cracks.
Key Takeaway: To construct a DFA for the complement of a language, take the original DFA and swap accepting states with non-accepting states—the structure stays identical, only the final verdict flips.