algorithm - 寻找 DFA 结构的补集

Question

所以我正在研究一种将 dfa 转换为其补码的方法。补码拒绝 dfa 接受的所有字符串，并接受 dfa 拒绝的所有字符串。为此，我应该遵循以下算法:“首先添加一个明确的死状态，并明确向它进行所有转换。其次将所有最终状态更改为非最终状态，并将所有非最终状态更改为最终状态。”

我尝试过这个，但没有成功。我不认为我理解正确。

首先，我将所有最终状态更改为非最终状态，并将非最终状态更改为最终状态。

然后对于每个状态，如果它没有字母表的转换，我会使用这些字母表添加从该状态到显式死状态的转换

这是正确的吗？

Answer 1

不，您应该首先为所有状态和符号转换到新创建的死状态，这样特定符号就不会从特定状态转换，在那之后您应该将所有状态设为最终状态状态非最终状态，反之亦然。当我们按照这个顺序执行时，死状态变为最终状态，这正是应该发生的事情(如果我们达到死状态，给定的字符串不被原始自动机接受。因此，它应该被它的补码接受)。