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，然后按照以前的方法交换状态。