finite-automata - 定义 r 和 r 的 DFA 时找到 r* 的 DFA

Question

我想要在定义 r 和 r 的 DFA 时找到 r* 的 DFA 的示例。又该如何思考？我读了一本教科书，但我没有清楚地理解。谢谢你。

Answer 1

r* 是包含所有字符串的语言，这些字符串是来自 r 的 0,1,2,3,4,... 字符串的串联。因此，r* 的明显 FA 是可以运行 r 0,1,2,3,4,... 次的 DFA 并在其中任何一次运行后接受。从任何接受状态到开始状态的 lambda/empty 转换将实现 1 次或多次运行。由此产生的自动机不再是确定性的。您可以使用标准方法来确定它。此构造不会将空字符串添加到自动机的语言中。如果它已经存在于 r 中，则没有必要。否则，您需要在自动机中为 r* 添加一种接受空字符串的方法，例如使用新的开始状态。

在消除空转换方面有一点经验，您还可以更直接地为简单的情况构建 DFA。