Course contentsShow
← Computer Science
Lesson 1785 of 2,87240. Theory of Computation: Regular LanguagesFree lesson

Complementing DFAs

Constructing a DFA for the complement language by swapping accept and non-accept states in the original DFA.

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):

  1. Keep the same states (Q)
  2. Keep the same alphabet (Σ)
  3. Keep the same transition function (δ)
  4. Keep the same start state (q₀)
  5. 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.