Number of words of a given length in a regular language

Question

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}

Answer 1

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}}$) .