補集構造法（complement construction）

如果你有一台機器，對「你要的」字串都說「是」，那要怎麼得到一台對「其餘所有」字串說「是」的機器？對確定型有限自動機（DFA）來說，答案出奇地簡單：把每盞燈都翻轉。原本接受的地方改成拒絕，原本拒絕的地方改成接受。其餘一切——狀態、轉移、起始狀態——完全不變。

精確地說：取一台辨識字母表 Σ（Sigma）上語言 L 的 DFA M，把它的接受狀態改為非接受狀態、反之亦然（新的接受集是 Q 減 F，其中 F 是舊的接受集），就得到 M'。則 M' 辨識 L 的補集，記作 L-bar 或 Σ* 減 L：M 拒絕的、Σ 上的每一個字串。這之所以成立，是因為 DFA 是「完全的」（total）且「確定的」（deterministic）——對任何輸入，它都恰好沿一條路徑走到恰好一個最終狀態，而那個狀態若非接受、便是非接受。因此「M 接受 w」與「M' 接受 w」逐字串恰好相反。

兩個提醒讓這件事誠實無誤。第一，DFA 必須是「完整的」：每個狀態對每個符號都要有轉移，否則「缺漏」的轉移會悄悄地拒絕，翻轉標籤就會得到錯誤答案——必要時先加一個死狀態（trap state）。第二，這個把戲「不能」直接套用在 NFA 上對調接受狀態：NFA 只要「某一條」路徑接受就接受，所以翻轉它的標籤並不會得到補集。要對 NFA 取補集，須先用子集構造法轉成 DFA，再對調。