Número de palavras de um determinado comprimento em um idioma regular

Existe uma caracterização algébrica do número de palavras de um determinado comprimento em um idioma regular?

A Wikipedia declara um resultado um tanto impreciso:

Para qualquer linguagem regular $L$ , existem constantes $\lambda_1,\,\ldots,\,\lambda_k$ e polinómios$p_1(x),\,\ldots,\,p_k(x)$ tal que para cada$n$ o número$s_L(n)$ de palavras de comprimento$n$ em$L$ satisfaz a equação $s_L(n)=p_1(n)\lambda_1^n+\dotsb+p_k(n)\lambda_k^n$ .

Não é afirmado que espaço o $\lambda$ é ao vivo em ( $\mathbb{C}$ , presumo) e se a função é necessário ter valores inteiros não negativos sobre toda a $\mathbb{N}$ . Eu gostaria de uma declaração precisa e um esboço ou referência para a prova.

Pergunta bônus: o inverso é verdadeiro, ou seja, dada uma função dessa forma, sempre existe uma linguagem regular cujo número de palavras por comprimento é igual a essa função?

_{Esta questão generaliza Número de palavras no idioma normal $(00)^*$}

Dada uma linguagem regular , considere alguns DFA aceitando L , seja A sua matriz de transferência ( A i j é o número de arestas que conduzem do estado i ao estado j ), seja x o vetor característico do estado inicial e seja y seja o vetor característico dos estados aceitantes. Então s L ( n ) = x T A n y $L$$L$$A$$A_{ij}$$i$$j$$x$$y$

$$s_L(n) = x^T A^n y.$$

O teorema de Jordan afirma que, sobre os números complexos, é semelhante a uma matriz com blocos de uma das formas ( λ ) , ( λ 1 0 λ ) , ( λ 1 0 0 λ 1 0 0 λ ) , ( λ 1 0 0 0 λ 1 0 0 0 λ 1 0 0 0 λ ) , … Se λ ≠ 0 , então $A$

$$\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$$ $\lambda \neq 0$$n$As potências desses blocos são Aqui é como chegamos a essas fórmulas: escrever o bloco comoB=λ+N. Potências sucessivas deNsão diagonais secundárias sucessivas da matriz. Usando o teorema do binômio (usando o fato de queλcomuta comN), Bn=(λ+n)N= $$\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$$ $B = \lambda + N$$N$$\lambda$$N$ Quandoλ=0, o bloco é nilpotentes, e obtemos as seguintes matrizes (a notação[n=k]é1sen=ke0de outro modo): ( [ n = 0 ] ),( [ n = 0 ] [ n = 1 ] 0 [ n = $$B^n = (\lambda + n)^N = \lambda^n + n \lambda^{n-1} N + \binom{n}{2} \lambda^{n-2} N^2 + \cdots.$$ $\lambda = 0$$[n = k]$$1$$n=k$$0$ $$\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}$$

$A^n$$\binom{n}{k} \lambda^{n-k}$$[n=k]$

$$s_L(n) = \sum_i p_i(n) \lambda_i^n + \sum_j c_j [n=j],$$ $\lambda_i,c_j$$p_i$$n$ $$s_L(n) = \sum_i p_i(n) \lambda_i^n.$$

$s_L(n)$$\lambda_i$$\lambda_1$

$$s_L(n) = p_1(n) \lambda_1^n (1 + o(1)).$$ $\lambda$$d$$s_L$$n$$d$$\lambda$$d$$p_0,\ldots,p_{d-1}$$\lambda_0,\ldots,\lambda_{d-1}$ $$s_L(n) = n^{p_{n\pmod{d}}} \lambda_{n\pmod{d}}^n (1 + o(1)).$$

$L \subseteq \Sigma^*$

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

$L_n = L \cap \Sigma^n$$|L_n|=s_L(n)$

$L(z)$

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

$P,Q$$L$$L(z)$

$Q$$|L_n|$$(|L_n|)_{n \in \mathbb{N}}$)