Search code examples
algorithmautomatadfanfakleene-star

How to apply Kleene star on automata?

I know how to apply Kleene star on language but I'm not sure how would I apply it to DFA or NFA. I'm pretty sure it would need to be epsilon NFA with initial state that is final and final states might need epsilon transition to that initial state?

Is there any algorithm for this? How would this DFA that accepts words that starts with 0 and end with 1 look after Kleene star was applied to it? enter image description here

Solution

  • In at least one proof I've seen of the equivalence of regular expressions and finite automata, a construction is given to show how to turn a NFA with a language corresponding to that of a regular expression s into a NFA with a language corresponding to that of the expression s*. I think the construction goes like this:

    1. new initial state q0' that is also accepting
    2. lambda/epsilon/empty transition from q0' to the former initial state q0
    3. lambda/epsilon/empty transitions from every accepting state (except q0') back to q0'

    This allows:

    1. the empty string to be accepted, even if it wasn't before
    2. any concatenation of strings from the language of the original NFA to be accepted