# Number of words of a given length in a regular language

Is there an algebraic characterization of the number of words of a given length in a regular language?

Wikipedia states a result somewhat imprecisely:

For any regular language $L$ there exist constants $\lambda_1,\,\ldots,\,\lambda_k$ and polynomials $p_1(x),\,\ldots,\,p_k(x)$ such that for every $n$ the number $s_L(n)$ of words of length $n$ in $L$ satisfies the equation $s_L(n)=p_1(n)\lambda_1^n+\dotsb+p_k(n)\lambda_k^n$.

It's not stated what space the $\lambda$'s live in ($\mathbb{C}$, I presume) and whether the function is required to have nonnegative integer values over all of $\mathbb{N}$. I would like a precise statement, and a sketch or reference for the proof.

Bonus question: is the converse true, i.e. given a function of this form, is there always a regular language whose number of words per length is equal to this function?

This question generalizes Question about the number of words in a regular language

-
a sketch of a proof is here –  Artem Kaznatcheev Apr 4 '12 at 20:49
@ArtemKaznatcheev Interesting, thanks. Would you consider moving your answer to this question, which it fits better? –  Gilles Apr 4 '12 at 20:52
I feel that this question is a little redundant (although more general). Generalizing my approach to the proof is a little hairy, but I will take a look after dinner. –  Artem Kaznatcheev Apr 4 '12 at 21:07
@ArtemKaznatcheev Thanks. I had trouble with the second part of your answer, extending to reducible DFAs. –  Gilles Apr 4 '12 at 21:10
hope ppl are not "reinventing the wheel here"... seems like this question is somewhat fundamental & that there ought to be ref/analysis in the literature somewhere? currently there are two wikipedia math refs to tying zeta functions to counting regular expressions & am wondering if these cases are handled there or are possibly special cases. Honkala 1989 & Berstel/Reutenauer 1990. also, wonder if anyone has implemented this in code or a math package (eg mathematica etc), how that would look.... –  vzn Sep 22 at 1:18
show 1 more comment

## 2 Answers

Given a regular language $L$, consider some DFA accepting $L$, let $A$ be its transfer matrix ($A_{ij}$ is the number of edges leading from state $i$ to state $j$), let $x$ be the characteristic vector of the initial state, and let $y$ be the characteristic vector of the accepting states. Then $$s_L(n) = x^T A^n y.$$

Jordan's theorem states that over the complex numbers, $A$ is similar to a matrix with blocks of one of the forms $$\begin{pmatrix} \lambda \end{pmatrix}, \begin{pmatrix} \lambda & 1 \\ 0 & \lambda \end{pmatrix}, \begin{pmatrix} \lambda & 1 & 0 \\ 0 & \lambda & 1 \\ 0 & 0 & \lambda \end{pmatrix}, \begin{pmatrix} \lambda & 1 & 0 & 0 \\ 0 & \lambda & 1 & 0 \\ 0 & 0 & \lambda & 1 \\ 0 & 0 & 0 & \lambda \end{pmatrix}, \ldots$$ If $\lambda \neq 0$, then the $n$th powers of these blocks are $$\begin{pmatrix} \lambda^n \end{pmatrix}, \begin{pmatrix} \lambda^n & n\lambda^{n-1} \\ 0 & \lambda^n \end{pmatrix}, \begin{pmatrix} \lambda^n & n\lambda^{n-1} & \binom{n}{2} \lambda^{n-2} \\ 0 & \lambda^n & n\lambda^{n-1} \\ 0 & 0 & \lambda^n \end{pmatrix}, \begin{pmatrix} \lambda^n & n\lambda^{n-1} & \binom{n}{2}\lambda^{n-2} & \binom{n}{3}\lambda^{n-3} \\ 0 & \lambda^n & n\lambda^{n-1} & \binom{n}{2}\lambda^{n-2} \\ 0 & 0 & \lambda^n & n\lambda^{n-1} \\ 0 & 0 & 0 & \lambda^n \end{pmatrix}, \ldots$$ Here's how we got to these formulas: write the block as $B = \lambda + N$. Successive powers of $N$ are successive secondary diagonals of the matrix. Using the binomial theorem (using the fact that $\lambda$ commutes with $N$), $$B^n = (\lambda + n)^N = \lambda^n + n \lambda^{n-1} N + \binom{n}{2} \lambda^{n-2} N^2 + \cdots.$$ When $\lambda = 0$, the block is nilpotent, and we get the following matrices (the notation $[n = k]$ is $1$ if $n=k$ and $0$ otherwise): $$\begin{pmatrix} [n=0] \end{pmatrix}, \begin{pmatrix} [n=0] & [n=1] \\ 0 & [n=0] \end{pmatrix}, \begin{pmatrix} [n=0] & [n=1] & [n=2] \\ 0 & [n=0] & [n=1] \\ 0 & 0 & [n=0] \end{pmatrix}, \begin{pmatrix} [n=0] & [n=1] & [n=2] & [n=3] \\ 0 & [n=0] & [n=1] & [n=2] \\ 0 & 0 & [n=0] & [n=1] \\ 0 & 0 & 0 & [n=0] \end{pmatrix}$$

Summarizing, every entry in $A^n$ is either of the form $\binom{n}{k} \lambda^{n-k}$ or of the form $[n=k]$, and we deduce that $$s_L(n) = \sum_i p_i(n) \lambda_i^n + \sum_j c_j [n=j],$$ for some complex $\lambda_i,c_j$ and complex polynomials $p_i$. In particular, for large enough $n$, $$s_L(n) = \sum_i p_i(n) \lambda_i^n.$$ This is the precise statement of the result.

We can go on and obtain asymptotic information about $s_L(n)$, but this is surprisingly non-trivial. If there is a unique $\lambda_i$ of largest magnitude, say $\lambda_1$, then $$s_L(n) = p_1(n) \lambda_1^n (1 + o(1)).$$ Things get more complicated when there are several $\lambda$s of largest magnitude. It so happens that their angle must be rational (i.e. up to magnitude, they are roots of unity). If the LCM of the denominators is $d$, then the asymptotics of $s_L$ will very according to the remainder of $n$ modulo $d$. For some of these remainders, all $\lambda$s of largest magnitude cancel, and then the asymptotics "drops", and we have to iterate this procedure. The interested reader can check the details in Flajolet and Sedgewick's Analytic Combinatorics, Theorem V.3. They prove that for some $d$, integers $p_0,\ldots,p_{d-1}$ and reals $\lambda_0,\ldots,\lambda_{d-1}$, $$s_L(n) = n^{p_{n\pmod{d}}} \lambda_{n\pmod{d}}^n (1 + o(1)).$$

-
add comment

Let $L \subseteq \Sigma^*$ a regular language and

$\qquad \displaystyle L(z) = \sum\limits_{n \geq 0} |L_n|z^n$

its generating function, where $L_n = L \cap \Sigma^n$ and so $|L_n|=s_L(n)$.

It is known that $L(z)$ is rational, i.e.

$\qquad \displaystyle \frac{P(z)}{Q(z)}$

with $P,Q$ polynomials; this is easiest seen by translating a right-linear grammar for $L$ into a (linear!) equation system whose solution is $L(z)$.

The roots of $Q$ are essentially responsible for the $|L_n|$, leading to the form stated on Wikipedia. This is immediately related with the method of characteristic polynomials for solving recurrences (via the recurrence which describes $(|L_n|)_{n \in \mathbb{N}}$) .

-
It is not clear how your answer answers the question. Also, what is $L_n$? –  Dave Clarke Apr 4 '12 at 21:57
@Gilles Analytic Combinatorics, the books by Eilenberg, the book by Berstel, Reutenauer –  uli Apr 5 '12 at 7:22
–  uli Apr 5 '12 at 7:30
@Patrick87: 1) Right, typo; thanks! 2) For finite languages, the generating function is a polynomial (and therewith rational). As $Q(z)=1$, this approach won't work. The linked theorem starts with a linear homogeneous recurrence; I don't think those can describe sequences that are zero for all $k \geq n_0$ (and non-zero for at least one value). Not sure, though. If I am right, the statement we are talking about does indeed only hold for infinite regular languages; this would not be entirely surprising as finite languages do not have any structure. –  Raphael Apr 5 '12 at 16:39
@Raphael Yeah, my thinking was similar... that seems to be a fairly serious shortcoming in the presentation of the theorem, if it doesn't hold for finite languages, since (a) finite languages are regular, (b) the theorem implies finite languages aren't regular, and (c) determining whether a language is finite is (in general) undecidable... I mean, Myhill-Nerode and the pumping lemma don't have that problem; they work for finite languages. –  Patrick87 Apr 5 '12 at 17:18
show 2 more comments