Automata Theory 简明教程

如果 (Q, ∑, δ, q0, F) 是接受语言 L 的 DFA，则可以通过将接受状态与非接受状态以及反之互换来获得 DFA 的补集。

我们将举例并在下面详细说明 −

此 DFA 接受语言

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

在字母表上

∑ = {a, b}

所以，RE = a+。

现在，我们将它的接受状态与其不接受状态互换，反之亦然，并且将获得以下状态：

此 DFA 接受语言

Ľ = {ε, b, ab、bb、ba、…​…​…​…​…​ }

在字母表上

∑ = {a, b}

Note - 如果我们希望对 NFA 求补，我们必须首先将其转换为 DFA，然后像在前面的方法中一样交换状态。