無法理解Kleene Star紙

Question

我正在閱讀關於編程語言工程和編譯器（6.035 Fall 2005 MIT課程）的論文。下面的頁面應該解釋Kleene Star運算符的工作原理，但我不明白它的意思。

全.PDF可以發現here。

Answer 1

它展示瞭如何構建一個NFA的R *給出一個NFA的R（這是在中間的橢圓形）。你會引入一個新的開始狀態和一個新的接受狀態。

Kleene星號允許零長度的話，那麼您包括新的開始狀態到新接受國家的ε轉變。

此外，要允許爲r的任何單詞的任何級聯。因此，包含從新開始狀態到舊開始狀態的轉換，以及從舊接受狀態到新接受狀態的轉換。這基本上可以讓你從新的開始狀態轉到使用epsilon的舊開始狀態，然後使用從r到舊的接受狀態的任何單詞，然後用epsilon轉到新的接受狀態（因此，從新的r中的任何單詞開始狀態到新的接受狀態）。

此外，要允許級聯。這就是爲什麼包含從舊接受狀態到舊開始狀態的epsilon轉換的原因。因此，當你到達舊的接受狀態時，你總是可以回到舊的開始狀態來追加r的另一個單詞。