Define the complexity of a regular language as the number of states of its minimal automaton. Let $$ \mathcal{A} $$ (respectively $$ \mathcal{A}' $$ ) be an n-state (resp. n’-state) deterministic and connected unary automaton. Our main results can be summarized as follows: 1.
The probability that $$ \mathcal{A} $$ is minimal tends toward 1/2 when n tends toward infinity
2.
The average complexity of $$ L{\text{(}}\mathcal{A}{\text{)}} $$ is equivalent to n
3.
The average complexity of $$ L{\text{(}}\mathcal{A}{\text{)}} \cap L{\text{(}}\mathcal{A}'{\text{)}} $$ is equivalent to $$ \frac{{3\zeta (3)}} {{2\pi ^2 }}nn' $$ , where ζ is the Riemann “zeta”-function.
4.
The average complexity of $$ L{\text{(}}\mathcal{A}{\text{)}}^ * $$ is bounded by a constant
5.
If n ≤ n’ ≤ P(n), for some polynomial P, the average complexity of $$ L{\text{(}}\mathcal{A}{\text{)}}L{\text{(}}\mathcal{A}'{\text{)}} $$ is bounded by a constant (depending on P).
Remark that results 3, 4 and 5 differ perceptibly from the corresponding worst case complexities, which are
nn’ for intersection, (
n − 1)
2 + 1 for star and
nn’ for concatenation product.