  We prove that, for any arbitrary finite alphabet and for the uniform
distribution over deterministic and accessible automata with n states, the
average complexity of Moore's state minimization algorithm is in O(n log n).
Moreover this bound is tight in the case of unary utomata.
