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，然后像之前的方法一样交换状态。