DFA 适用于具有偶数个 0 或恰好包含两个 1 的所有二进制字符串

Question

这个问题我有点困惑。我试图自己想出一个解决方案，到处引用了一些类似的问题，但我不确定这是否正确。为此构建 NFA 很容易，但 DFA 让我很困惑。我在下面插入了我所做的事情的图片，但我不知道它是否正确。

我不知道是否需要包括死亡/陷阱状态F，但我读过一个类似的问题做同样的事情，所以我只是跟着它。 F 被包括在内有什么原因吗？有没有一种方法可以在不使用它的情况下解决问题？

Answer 1

通过取并集，您设计了一个接受两种语言的并集的 DFA，即，当输入具有偶数个“0”，或恰好具有两个“1”（或两者）时，它接受输入。但你需要两种语言的交集。

幸运的是，修复很简单：交集是 𝐹 = {𝐴𝐸}

因此，在最终的图中，只有状态 𝐴𝐸 应该是接受状态。其他州均不接受州。