如何找到两个NFA的交集

Question

在DFA中，我们可以通过对两个自动机的状态进行叉积，并接受那些在两个初始自动机中都被接受的状态来进行两个自动机的交集操作。

联合操作类似进行。然而，虽然我可以很容易地使用epsilon转换在NFA中执行并集操作，但如何执行它们的交集操作呢？

- Aditya Nambiar

Answer 1

你可以像处理DFA一样使用跨产品构造方法来处理NFA。唯一不同的是你需要如何处理ε转移。具体来说，对于跨产品自动机中的每个状态(q_i, r_j)，你需要添加一个ε转移从该状态到由两台机器的第一台机器的q_i到q_k存在ε转移和由第二个机器的r_j到r_k存在ε转移的状态对(q_k, r_j)以及每个状态对(q_i, r_k)，其中第一台机器中从q_i到q_k和第二台机器中从r_j到r_k都存在ε转移。

另外，你也可以将NFA转换为DFA，然后计算这些DFA的交叉积。

希望这会有所帮助！

- templatetypedef

---

那么就没有像并集那样简单的方法，只需添加 epsilon 吗？ - Aditya Nambiar

@AdityaNambiar- 据我所知并不是最好的选择。 - templatetypedef

这里的另一个答案提出了一个关于缺少“同时ε转换”的问题，即两个机器同时进行ε转换。我还没有发现省略它们会有什么问题，因为那些转换可以通过几个步骤来完成，但也许存在一些奇怪的边缘情况。你能澄清一下吗？ - harold

@harold 我认为你不需要显式地处理这种情况，因为即使上述构造没有直接包括从初始对到目标对的转换，你仍然可以想象在第一个机器中跟随 ε-转换，然后在第二个机器中进行 ε-转换，这样就形成了两个 ε 的链。 - templatetypedef

@AdityaNambiar 如果你想要像联合案例那样简单的方法，你需要使用交替自动机而不是非确定性自动机。这也将允许您有效地执行语言补集（因此所有有用的布尔运算，例如包含）。问题再次在于AFA的更难模拟和分析。 - pallly

没关系，我撤回我的评论。 - xFioraMstr18

Answer 2

我们还可以使用德摩根定理：A 交 B = (A' U B')'

取两个NFA的补集的并集相对较简单，尤其是如果您习惯于使用epsilon方法进行并集。

- aneena

---

除了先将其转换成 DFA 之外，如何对 NFA 进行否定处理？ - Stefan

虽然这个答案是正确的，但补集确实需要通过幂集构造转换为DFA——对于所有三个补集，因为epsilon方法会创建另一个NFA。最坏情况是指数级别的，至少是O(2^n)。 （潜在的“2^2^n”情况存在，但我不确定是否真的存在。） - Christoph Burschka

Answer 3

templatetypedef 的回答中存在一个严重错误。

L1 和 L2 是非确定有限状态自动机，它们的积自动机：

新状态 Q = L1 和 L2 状态的积。

现在是转移函数:

a 是两个自动机字母表的并集中的符号。

delta( (q1,q2) , a) = delta_L1(q1 , a) X delta_L2(q2 , a)

这意味着应该将 delta_L1(q1 , a) 的结果与 delta_L2(q2 , a) 的结果相乘得到集合。

templatetypedef 的回答中存在的问题是没有提到积的结果 (qk, rk)。

- KFkf

---

请注意，Harold和templatetypedef已经在templatetypedef的回答下讨论了这个问题，看起来这并不是一个问题。 - MattS

Answer 4

可能有点晚，但因为我今天遇到了类似的问题，所以想分享一下。首先要理解交集的含义。在这里，它意味着给定字符串e，e应该被两个自动机都接受。

考虑以下自动机：

1. m1 接受包含子串'11'的语言{w | w}
2. m2 接受包含子串'00'的语言{w | w}

直观地说，m=m1∩m2是接受同时包含'11'和'00'作为子串的字符串的自动机。这个想法是同时模拟两个自动机。

现在让我们正式定义交集。

m=(Q, Σ, Δ, q0, F)

让我们从定义m的状态开始; 如上所述，这是m1和m2中状态的笛卡尔积。因此，如果我们将a1，a2作为m1中状态的标签，将b1，b2作为m2中的状态，则Q将包含以下状态：a1b1，a2b1，a1b2，a2b2。此产品构造背后的思想是跟踪我们在m1和m2中的位置。

Σ很可能保持不变，但在某些情况下它们会有所不同，我们只需取m1和m2中字母表的并集即可。

q0现在是包含m1的起始状态和m2的起始状态的Q中的状态。（以a1b1为例。）

F包含状态s当且仅当s中提到的两个状态分别是m1和m2的接受状态。

最后是Δ；我们再次根据笛卡尔积来定义delta，如下所示：Δ（a1b1，E）=Δ（m1）（a1，E）xΔ（m2）（b1，E），正如上面的一个答案中所提到的一样（如果我没有记错的话）。 Δ这种构造的直观思想就是将a1b1分开，并考虑原始自动机中的a1和b1状态。现在我们'迭代'每个可能的边缘，以E为例，看看它在原始自动机中带我们到哪里。之后，我们使用笛卡尔积将这些结果粘合在一起。如果（a1，E）存在于m1中但不是Δ（b1，E）在m2中，则该边缘将不存在于m中;否则我们将有某种联合构造。

- LaurensVijnck

---

你不应该定义Δ来接收一个边缘而不是一个字符（Σ的元素）。另外，你可以更平行地编写“If (a1， E)在m1中存在但Δ（b1，E）在m2中不存在”的代码（例如，“如果(a1，E)在m1中存在但(b1，E)在m2中不存在”）。 - xFioraMstr18

Answer 5

构建产品自动机的另一种选择是允许更复杂的接受标准。通常，当NFA到达一组接受终态中的任何一个时，它会接受输入字符串。这可以扩展为状态的布尔组合。具体而言，您为交集构造自动机，就像为联合构造自动机一样，但是只有在两个自动机中都处于（相应的）接受终态时，才认为所得到的自动机接受输入字符串。

- Björn Höhrmann