1

所以我正在研究一种将 dfa 转换为补码的方法。补码拒绝 dfa 接受的所有字符串，并接受 dfa 拒绝的所有字符串。为此，我应该遵循这个算法：“首先添加一个显式的死状态并显式地对其进行所有转换。然后将所有最终状态更改为非最终状态，并将所有非最终状态更改为最终状态。”

我对此进行了一次尝试，但没有成功。我不认为我理解正确。

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

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

这个对吗？

4

1 回答 1

0

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

于 2015-03-06T20:09:48.887 回答