如何找到 D FA 的闭包

Question

我正在尝试实现关闭D FA。我在不使用 N FA 的情况下成功地实现了 D FA 的并集、互补交集、减法和连接。我们的老师没有告诉我们找到闭包的算法。我试图通过将 D FA 连接到自身来做到这一点，但很明显它没有用。

我只需要通过使用矩阵表示 D FA 的方式的步骤。另外，请详细说明 Klein 闭包，但我相信一旦我知道如何获得闭包，我就能做到。

Answer 1

我不确定您所说的闭包一般是什么意思。但是对于 Kleene 闭包，您可以这样进行：从每个最终状态添加一个 epsilon-transition（不读取任何内容）到起始状态。因此，读完一个单词后，您可以从另一个单词开始。

当然，生成的自动机不再是确定性的。但是有再次确定它的标准程序。

对于直接构造：查看所有进入最终状态的转换，例如 (q,a) -> f。从传出状态添加另一个读取相同符号并转到起始状态的转换：(q,a) -> s。所以自动机有可能读完这个词，然后再开始。