Number of necessary states in DFA/NFA.

Question

Say nX is the number of states in DFA X defined by the regular language L.

How many states wold you need in a DFA for the language L*? And how many states would you need in NFA for the language L*?

I would really appreciate any help on how to solve this, as i don't know where to start.

Answer 1

For upper bounds on the sizes of automata for $L^*$ we can reason as follows.

Given an automaton (either DFA or NFA) with $n$ states that accepts $L$, an NFA that accepts Kleene's closure $L^*$ can be built with $n+1$ states.

The construction is frequently used in proofs of Kleene's theorem, and is therefore found in most books that cover automata theory. Briefly, one adds a new state, both initial and final, and connects this state and all final states of the given automaton to the original initial state with $\epsilon$-transitions. The $\epsilon$-transitions may be eliminated without increasing the number of states.

The resulting automaton is in general an NFA even if the initial automaton was a DFA. Hence determinization may be needed, which in the worst case causes an exponential blow-up. So, the easy upper bound is $2^{n+1}$ states.

Answer 2

The optimal upper bound on a two-letter alphabet is $2^{n-1} - 2^{n-2}$. See [1, theorem 3.3, p. 121].

[1] Arto Salomaa, Kai Salomaa, and Sheng Yu. State complexity of combined operations. Theor. Comput. Sci., 383(2-3):140–152, 2007.