如果 DFA 被最小化，是否保证它的补码也被最小化？

If a DFA is minimized, is it guaranteed that it's complement is also minimized?

考虑有一个接受语言 L 的最小化 DFA。问题是找到其补码中的最少状态数。

现在，如果我取这个 DFA 的补码，即如果我将非最终状态设为最终状态，将最终状态设为非最终状态，我还需要担心最小化这个补码 DFA 吗？

DFA - 确定性有限自动机

让我们从 L1 被最小 DFA D1 接受开始。然后我们可以检索补码的 DFA（如您所述）。因此，让我们派生一个 DFA D2，它接受 L1'，它具有与 L1 相同数量的状态。

现在假设 D2 不是 L1'

的最小 DFA

我们应该能够进一步减少其中的状态数量以获得 DFA D3。但是得到 D3 的补码应该给我们一个新的 DFA D4 它接受 (L1')' 即 L1 但状态少于 D1 使其不是最小值L1 的 DFA。

所以我们假设 D2 不是 L1' 的最小值是错误的。