Search code examples
mathlanguage-agnosticautomatonkleene-star

Cannot understand Kleene Star paper

I'm reading a paper about programming languages engineering and compilers (6.035 Fall 2005 MIT course). The following page should explain the working principles of the Kleene Star operator, but I cannot understand what it means.

1

The full .pdf can be found here.

Solution

  • It shows how you can construct an NFA for r* given an NFA for r (this is the ellipse in the middle). You would introduce a new start state and a new accept state.

    The Kleene star allows zero-length words, so you include an epsilon transition from the new start state to the new accept state.

    Additionally, you want to allow any concatenation of any word of r. So , include an epsilon transition from the new start state to the old one and one from the old accept state to the new one. This basically allows you to go from the new start state to the old one with epsilon, then with any word from r to the old accept state, and then with epsilon to the new accept state (hence, with any word from r from the new start state to the new accept state).

    Additionally, you want to allow concatenations. That's why you include the epsilon transition from the old accept state to the old start state. Hence, when you arrive at the old accept state, you can always go back to the old start state to append another word from r.