看不懂 Kleene Star 纸

Question

我正在阅读一篇关于编程语言工程和编译器的论文（2005 年秋季麻省理工学院课程 6.035）。下一页应该解释一下Kleene Star算子的工作原理，但是我看不懂是什么意思

可以找到完整的 .pdf here。

Answer 1

它展示了如何在给定 r 的 NFA 的情况下为 r* 构建 NFA（这是中间的椭圆）。您将引入一个新的开始状态和一个新的接受状态。

Kleene star 允许零长度单词，因此您包括从新开始状态到新接受状态的 epsilon 转换。

此外，您希望允许 r 的任何单词的任何串联。因此，包括从新开始状态到旧状态的 epsilon 转换，以及从旧接受状态到新状态的转换。这基本上允许您使用 epsilon 从新的开始状态转到旧的开始状态，然后使用 r 中的任何单词进入旧的接受状态，然后使用 epsilon 进入新的接受状态（因此，来自 r 的任何单词来自新的接受状态开始状态到新的接受状态）。

此外，您希望允许串联。这就是为什么你包括从旧的接受状态到旧的开始状态的 epsilon 转换。因此，当您到达旧的接受状态时，您总是可以返回到旧的开始状态以从 r 添加另一个词。