# 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

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
This is a nice idea, but there are many steps I don't follow. Do you have an explanation or a good reference for the “known” bits? – Gilles Apr 4 '12 at 23:29
@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
Two questions: First, in the generating function, you mean $n \geq 0$, right? Second, does this proof work for finite languages? More generally, does the theorem from Wikipedia work for languages where $s_L(k) = 0$ where $k > n_0$, for some finite $n_0$? If so, could you produce some $p_i$ and $\lambda_i$ for the language $\{\epsilon\}$? – Patrick87 Apr 5 '12 at 13:04