Deterministic Finite Automaton of Kleene Star

Question

I read that every Non-deterministic Finite Automaton (NFA) can be transferred into a Deterministic Finite Automaton (DFA). Can this be done for kleene star regex, say a*?

Above is the NFA for a*.

Answer 1

Yes. A Kleene star deterministic finite automaton has two states. The starting state is final, and has a transition to itself for a, and a transition to the other state for all other symbols. The other state has a transition to itself for every symbol.

Thus, it accepts the empty string (since the starting state is final) and an arbitrary number of repetitions of a. Anything that is not a will send the DFA into the other state, which is non-final, and from which there is no escape.

It gets slightly more complicated if you apply the Kleene star to a regular expression more complicated than a single symbol, but it can always be done: simply insert the NFA for the regular expression into the red part of the image you showed, and apply the standard Powerset construction algorithm to convert the NFA to a DFA. I strongly recommend studying this algorithm; if you understand why it works, you will see why every NFA can be converted into a DFA.

Answer 2

It is just a single starting state which also is the accepting state. It has a self loop which accepts 'a'.