所以我正在研究一种将 dfa 转换为其补码的方法。补码拒绝 dfa 接受的所有字符串，并接受 dfa 拒绝的所有字符串。为此，我应该遵循以下算法: “首先添加一个明确的死状态，并明确向它进行所有转换。其次将所有最终状态更改为非最终状态，并将所有非最终状态更改为最终状态。”
我尝试过这个，但没有成功。我不认为我理解正确。
首先，我将所有最终状态更改为非最终状态，并将非最终状态更改为最终状态。
然后对于每个状态，如果它没有字母表的转换，我会使用这些字母表添加从该状态到显式死状态的转换
这是正确的吗？
最佳答案
不，您应该首先为所有状态和符号转换到新创建的死状态，这样特定符号就不会从特定状态转换，在那之后您应该将所有状态设为最终状态状态非最终状态，反之亦然。当我们按照这个顺序执行时，死状态变为最终状态，这正是应该发生的事情(如果我们达到死状态，给定的字符串不被原始自动机接受。因此，它应该被它的补码接受)。
关于algorithm - 寻找 DFA 结构的补集，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28905900/