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*.

Protoactinium

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.

Gallup

Answer 2

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

Protoactinium

Why, then, is the Kleene closure DFA necessary? As in OP's image. Why are the epsilon necessary when they can be represented with just one state – Hazelwood

It can only be represented with one state if the operand of the kleene star is a single symbol. The epsilon transitions make the NFA general enough to handle any regular expression under the kleene star. – Fluorinate