The average state complexity of the star of a finite set of words is linear.

We prove that, for the uniform distribution over all sets X of m (that is a fixed integer) non-empty words whose sum of lengths is n, D_X, one of the usual deterministic automata recognizing X*, has in average O(n) states and that the state complexity of X* is Theta(n). We also show that the average time complexity of the computation of the automaton D_X is O(n log n), when the alphabet is of size at least three.