Abstract:
The main quantitative characteristics of a language $L$ over a finite alphabet $\Sigma$ is the function $C_L(n)=|L\cap\Sigma^n|$ called the combinatorial complexity of $L$. We relate the type and parameters of the asymptotic behaviour of this function for a regular language $L$ to the parameters of the corresponding finite automaton. Then we give efficient algorithms to calculate such parameters of finite automata. Using these results, we describe the oscillations of combinatorial complexity for arbitrary, prefix, and factorial regular languages.