# Asymptotics of the number of words in a regular language of given length

For a regular language $L$, let $c_n(L)$ be the number of words in $L$ of length $n$. Using Jordan canonical form (applied to the unannotated transition matrix of some DFA for $L$), one can show that for large enough $n$, $$c_n(L) = \sum_{i=1}^k P_i(n) \lambda_i^n,$$ where $P_i$ are complex polynomials and $\lambda_i$ are complex "eigenvalues". (For small $n$, we may have additional terms of the form $C_k[n=k]$, where $[n=k]$ is $1$ if $n=k$ and $0$ otherwise. These correspond to Jordan blocks of size at least $k+1$ with eigenvalue $0$.)

This representation seems to imply that if $L$ is infinite then asymptotically, $c_n(L) \sim C n^k \lambda^n$ for some $C,\lambda>0$. However, this is patently false: for the language $L$ over $\{0,1\}$ of all words of even length, $c_{2n}(L) = 2^{2n}$ but $c_{2n+1}(L) = 0$. This suggests that for some $d$ and for all $a \in \{0,\ldots,d-1\}$, either $c_{dm+a}(L) = 0$ for large enough $m$ or $c_{dm+a} \sim C_a (dm+a)^{k_a} \lambda_a^{dm+a}$. This is proved in Flajolet & Sedgewick (Theorem V.3), who attribute the proof to Berstel.

The proof provided by Flajolet and Sedgewick is somewhat technical; so technical, in fact, that they only sketch it. I attempted a more elementary proof using Perron-Frobenius theory. We can regard the transition graph of the DFA as a digraph. If the digraph is primitive then the result follows almost directly from the Perron-Frobenius theorem. If the digraph is irreducible but imprimitive with index $r$, then by considering the "$r$th power" of the DFA (each transition corresponds to $r$ symbols), we get the same result. The difficult case is when the digraph is reducible. We can reduce to the case of a path of strongly connected components, and then we get the result by estimating sums of the form $$\sum_{m_1+\cdots+m_k=m} \prod_{i=1}^k \lambda_i^{m_i}.$$ (Each such sum corresponds to a particular way of accepting a word, going through the different components in a certain way.) This sum, in turn, can be estimated by pinpointing the largest term, which corresponds to $m_i \propto \log \lambda_i$. For every eigenvalue which is repeated $r$ times, we get an extra factor of $\Theta(m^{r-1})$.

The proof has its rough edges: in the reducible case, we need to pass from terms asymptotic to $C \lambda_i^m$ to the sum mentioned above, and then we need to estimate the sum.

The proof by Flajolet and Sedgewick is perhaps simpler, but less elementary. Its starting point is the rational generating function of $c_n(L)$, and it involves induction on the number of pole magnitudes (!). The basic idea is that all eigenvalues of maximal modulus are roots of unity (if normalized by their modulus), due to a (moderately easy) theorem of Berstel. Choosing an appropriate $d$ and looking at words of length $dm+a$, all these eigenvalues become real. Considering the partial fraction expansion, we get that if the eigenvalue of maximal modulus "survives", then it determines the asymptotics, which are of the form $Cn^k\lambda^n$. Otherwise, we find a new rational generating function which corresponds just to words of this length (using an Hadamard product), and repeat the argument. The aforementioned quantity keeps decreasing, and so eventually we find the desired asymptotics; $d$ might have to grow in the process, to reflect everything that happens in the inductive steps.

Is there a simple and elementary proof for the asymptotic property of $c_n(L)$?

• Which "asymptotic property" are you referring to, the one right at the top? – Raphael Apr 16 '13 at 9:30
• Exactly that property. – Yuval Filmus Apr 16 '13 at 17:19
• For the reducible case, are there no simple combinatorial bounds (perhaps obtained by considering subsets of paths, and multisets of paths)? – András Salamon Apr 27 '13 at 17:27
• There are easy bounds, but you probably lose polynomial factors there. There is a sum with polynomially many terms, and we can estimate it using the largest term. However, this isn't going to give us the correct asymptotic, since the other terms decay quite quickly. Perhaps an estimate with an integral is possible, but that is already getting a bit messy. – Yuval Filmus Apr 28 '13 at 4:47
• generally, finding alternative or more elementary proofs of problems can be very hard and is mostly a theoretical exercise... is there any further motivation/bkg/application? suggest migrate to cstheory. – vzn Apr 30 '13 at 2:32

4.7.11 Proposition Let $B$ be a subset of $A^*$ that freely generates $B$. Then $B^*(\lambda)=(I-B(\lambda))^{-1}$