不完全 DFA 的叉积
Cross product of incomplete DFA's
我正在尝试在两个 DFA 之间进行叉积，但它们都是不完整的 DFA。
下图是我对两个不完全 DFA 的叉积的交集得出的答案。字母表是{a,b,c,d,e}。
这是正确的还是它们不完整的事实改变了一切？
如果您正在构建叉积以找到并集，那么它们不完整的事实确实会使您的工作变得不同；但是，对于交叉路口，您仍然可以使用这种基本方法。但是，你犯了一些错误：
让我们从左上角开始，查看状态 A1:
的所有转换
首先，您有一个标记为 c 的状态转换，从状态 A1 到状态 A2。但是，这是不正确的，因为在标有 c 的顶部 DFA 中没有从 A 到 A 的转换。然后，您有一个标记为 a 的转换，它从状态 A1 到自身。这也是不正确的，因为没有从状态 1 到任何标记为 a 的转换。同样，没有从状态 1 标记为 b 的过渡，因此这也会使您从 A1 到 B1 的过渡无效。
当使用不完整的 DFA 并像这样制作 cross-product 时，当存在状态 p 和状态的字母时，您将只有状态 (p,q) 的传出边q 有出边。
因此，没有离开开始状态的转换。在这一点上，我们可以停止工作，因为没有离开开始状态的转换，没有意义 - 生成的 DFA 不匹配。
解决此问题的另一种可能性是首先通过添加 non-accepting 状态（我称此状态为 ∅）来完成两个 DFA。对于还没有不同传出边的每个字母，该状态应该有一条从每个状态到它的边。例如，在第一个 DFA 中，对于 c、d 和 e，会有一条从 A 到 ∅ 的边。此外，每个字母都应该有一条从 ∅ 到 ∅ 的边。现在两个 DFA 都已完成。
当你这样做时，你最终会得到 A1 之外的边缘：A∅ 代表 a，B∅ 代表 b，∅1 表示 c，∅∅ 表示 d 和 e。剩下的留作练习，但如果你把它完全画出来，你会再次发现没有从A1到任何接受状态的路径。
实际上，如果您要构造 cross-product 来找到并集，那么首先完成两个 DFA 实际上是您需要做的 - 对于交集，允许简单地丢弃涉及 [=28= 的任何状态] 在任何一个 DFA 中，因为达到 ∅ 意味着你永远不会达到接受状态，但是对于联合你需要保留它们，因为一些涉及 ∅ 的状态可能正在接受 cross-product. （你仍然可以丢弃状态 ∅∅ 和它的任何边缘）
我正在尝试在两个 DFA 之间进行叉积，但它们都是不完整的 DFA。
下图是我对两个不完全 DFA 的叉积的交集得出的答案。字母表是{a,b,c,d,e}。
这是正确的还是它们不完整的事实改变了一切？
如果您正在构建叉积以找到并集，那么它们不完整的事实确实会使您的工作变得不同；但是，对于交叉路口，您仍然可以使用这种基本方法。但是，你犯了一些错误：
让我们从左上角开始，查看状态 A1:
首先，您有一个标记为 c 的状态转换，从状态 A1 到状态 A2。但是，这是不正确的，因为在标有 c 的顶部 DFA 中没有从 A 到 A 的转换。然后，您有一个标记为 a 的转换，它从状态 A1 到自身。这也是不正确的，因为没有从状态 1 到任何标记为 a 的转换。同样，没有从状态 1 标记为 b 的过渡，因此这也会使您从 A1 到 B1 的过渡无效。
当使用不完整的 DFA 并像这样制作 cross-product 时，当存在状态 p 和状态的字母时，您将只有状态 (p,q) 的传出边q 有出边。
因此，没有离开开始状态的转换。在这一点上，我们可以停止工作，因为没有离开开始状态的转换，没有意义 - 生成的 DFA 不匹配。
解决此问题的另一种可能性是首先通过添加 non-accepting 状态（我称此状态为 ∅）来完成两个 DFA。对于还没有不同传出边的每个字母，该状态应该有一条从每个状态到它的边。例如，在第一个 DFA 中，对于 c、d 和 e，会有一条从 A 到 ∅ 的边。此外，每个字母都应该有一条从 ∅ 到 ∅ 的边。现在两个 DFA 都已完成。
当你这样做时，你最终会得到 A1 之外的边缘：A∅ 代表 a，B∅ 代表 b，∅1 表示 c，∅∅ 表示 d 和 e。剩下的留作练习，但如果你把它完全画出来，你会再次发现没有从A1到任何接受状态的路径。
实际上，如果您要构造 cross-product 来找到并集，那么首先完成两个 DFA 实际上是您需要做的 - 对于交集，允许简单地丢弃涉及 [=28= 的任何状态] 在任何一个 DFA 中，因为达到 ∅ 意味着你永远不会达到接受状态，但是对于联合你需要保留它们，因为一些涉及 ∅ 的状态可能正在接受 cross-product. （你仍然可以丢弃状态 ∅∅ 和它的任何边缘）