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, , one of the usual deterministic automata recognizing X ^*, has on average states and that the average state complexity of X ^* is Θ(n). We also show that the average time complexity of the computation of the automaton is , when the alphabet is of size at least three.