DFA補集

如果 (Q, ∑, δ, q₀, F) 是一個接受語言 L 的 DFA，那麼該 DFA 的補集可以透過交換其接受狀態和非接受狀態來獲得。

我們來看一個例子，並在下面詳細說明：

此 DFA 接受語言

L = {a, aa, aaa , ............. }

在字母表上

∑ = {a, b}

所以，RE = a⁺。

現在我們將交換其接受狀態和非接受狀態，並將得到以下結果：

此 DFA 接受語言

Ľ = {ε, b, ab ,bb,ba, ............... }

在字母表上

∑ = {a, b}

注意 - 如果要對 NFA 求補集，則必須先將其轉換為 DFA，然後像之前的方法一樣交換狀態。