computer-science - 两个确定性有限自动机的并集？

Question

我正在尝试解决一个问题，我必须为两种语言的联合创建一个 DFA。

它们是： {s 是 {a, b, c}*| s 中的每个 "a" 后面紧跟一个 "b"} 和

{ s 是 {a, b, c}*| s 中的每个 "c" 前面都紧跟着一个 "b"}

我认为我在正确的轨道上，但不确定它是否完全正确。有人可以看看吗？

Answer 1

这是一篇类似的文章，解释了如何找到两个 DFA 的并集。

要理解的关键是您必须同时运行两个 DFA，或者通常您必须在联合 DFA 中维护两个 DFA 的状态。

---

编辑：

您得到不正确结果的原因是因为您的 DFA 不是确定性的，并且因为它们实际上并不能决定您描述的语言。我认为您对联盟的计算是正确的，但您应该在继续之前修复您的 DFA。

Answer 2

两种语言的交集由L1 ∩ L2 = not(not(L1) ∪ not(L2))（根据德摩根定律）给出。

DFA的补码 ( "not") 是通过将所有接受状态更改为不接受来给出的，反之亦然。这将为您提供一个非确定性有限自动机 (NFA)。

联合是通过将您的两个 DFA 或 NFA 组合成一个同时接受两种语言的新 NFA 来创建的。这是通过引入一个启动状态来完成的，您可以从该状态进入两个 NFA 的启动状态，而无需消耗任何东西（仅消耗 ε）。

完成所有这些后，您就获得了 NFA。您可以使用常用方法将其简化为 DFA。