5

在 DFA 中，我们可以通过对两个自动机的状态进行叉积并接受在两个初始自动机中都接受的那些状态来计算两个自动机的交集。类似地执行联合。尽管我可以使用 epsilon 转换轻松地在 NFA 中进行联合，但我如何进行它们的交集？

4

5 回答 5

7

您可以像使用 DFA 一样在 NFA 上使用叉积构造。唯一的变化是你如何处理 ε-transitions。具体来说，对于叉积自动机中的每个状态 (q i , r j )，您从该状态添加一个 ε 转移到第一台机器中存在 ε 转移的每对状态 (q k , r j )从 q i到 q k以及到每对状态 (q i , r k )，其中第二台机器中存在从 r j到 r k的 ε 转换。

或者，您始终可以将 NFA 转换为 DFA，然后计算这些 DFA 的叉积。

希望这可以帮助！

于 2014-02-09T17:32:44.260 回答
3

我们也可以使用德摩根定律：A 交点 B = (A' U B')'

将两个 NFA 的赞美并集比较简单，特别是如果您习惯了 epsilon 的并集方法。

于 2014-11-04T14:26:43.320 回答
2

在 templatetypedef 的答案中有一个巨大的错误。

L1 和 L2 的乘积自动机是 NFA：

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

现在转换功能：

a 是两个自动机字母组合中的符号

delta( (q_1,q_2) , a) = delta_L1(q_1 , a) X delta_L2(q_2 , a)

这意味着您应该将 delta_L1(q_1, a) 的结果集与 delta_L2(q_1, a) 的结果集相乘。

模板类型定义的答案中的问题是没有提到产品结果（qk，rk）。

于 2015-04-15T04:35:20.420 回答
1

可能是一个迟到的答案，但由于我今天遇到了类似的问题，所以我想分享它。先搞清楚交点的意思。在这里，这意味着给定字符串e，e应该被两个自动机接受。

考虑以下自动机：

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

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

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

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

  • 让我们首先定义m的状态，正如上面提到的m1和m2中状态的 carthesian 乘积。因此，如果我们将a1 , a2作为m1中状态的标签，将b1 , b2作为m2中的状态标签，Q 将由以下状态组成：a1b1 , a2b1 , a1b2 , a2b2。这背后的含义是跟踪m1和m2中的位置。

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

  • q0 现在是 Q 中的状态，包含m1的开始状态和m2的开始状态。（a1b1，举个例子。）

  • F 包含状态s IF 并且仅当s中提到的两个状态分别是m1，m2的接受状态时。

  • 最后但并非最不重要的Δ；我们根据carthesian积再次定义delta，如下所示：我没有弄错。这背后的直观想法是将a1b1分开，并考虑其原始自动机中的状态a1和b1。现在我们“迭代”每个可能的边，例如选择 E，看看它在原始自动机中将我们带到哪里。之后，我们使用 carthesian 积将这些结果粘合在一起。如果 ( a1 , E) 存在于m1中，但不存在 Δ( b1 , E) 在m2边将不存在于m中，否则我们将有某种联合构造。

于 2015-11-24T23:35:30.230 回答
-2

构建产品自动机的另一种方法是允许更复杂的验收标准。通常，当 NFA 达到一组接受最终状态中的任何一个时，它就会接受输入字符串。这可以扩展到状态的布尔组合。具体来说，您可以像为并集一样为交集构造自动机，但考虑生成的自动机仅在它处于（对应于）接受两个自动机中的最终状态时才接受输入字符串。

于 2014-02-13T15:41:01.013 回答