5

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*?enter image description here

Above is the NFA for a*.

Ankit Shubham
  • 2,989
  • 2
  • 36
  • 61

2 Answers2

6

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.

Aasmund Eldhuset
  • 37,289
  • 4
  • 68
  • 81
1

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

enter image description here

Ankit Shubham
  • 2,989
  • 2
  • 36
  • 61
  • 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 – fjch1997 Jul 21 '19 at 02:25
  • 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. – Joshua Wise May 27 '21 at 19:19