A DFA for Kleene star operation

Question

What would be the highest number of states a DFA would have for a language L*? Is it possible to define a worst-case scenario here?

Answer 1

As Welbog points out, L* can have any number of states. This is not necessarily obvious though, so we might as well try to prove it. The proof is simple: we will describe a sequence of regular languages such that the minimum number of states in a DFA for the Nth language is equal to N.

Our regular languages will be {a}, {aa}, {aaa}, ..., that is, the sequence of finite regular languages consisting of a single non-empty string taken from the language a*, in ascending order of length.

A minimal DFA for the language {a}* has one state (assuming alphabet {a}) which loops to itself on a.

A minimal DFA for the language {aa}* has two states: the initial state is still accepting but we need a non-accepting state to accept strings with a number of a's not evenly divisible by two.

Generally, a minimal DFA for the language {a^n}* has n states: the initial state is still accepting but we need n-1 non-accepting states to keep track of the value of |w| % n. We must keep track of this value so that we can know if we have seen a number of a's that is evenly divisible by n, and in a DFA the only way to keep track of the number of a's seen so far is by changing to a new unique state.

This constructive proof allows us to offer evidence that there is no upper limit on the size of a minimal DFA for L*: if there were such a limit with m states, we'd simply point out that the language (a^(m+1))* must have a larger DFA.