math - 看不懂 Kleene Star 纸

Question

我正在阅读一篇关于编程语言工程和编译器的论文（6.035 Fall 2005 MIT course）。下面的页面应该解释了 Kleene Star 操作符的工作原理，但我无法理解它的含义。

完整的 .pdf 可以在这里找到。

Answer 1

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

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

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

此外，您希望允许连接。这就是为什么您包含从旧接受状态到旧开始状态的 epsilon 转换。因此，当您到达旧的接受状态时，您始终可以返回旧的开始状态以附加来自 r 的另一个单词。