Función generadora de un lenguaje regular

Question

Es bien sabido que la función de generación de un lenguaje regular $L$, es decir, $\sum n_kz^k$ donde $n_k$ es el número de palabras de longitud $k$ en $L$, es racional, es decir, un cociente de dos polinomios $P(z)/Q(z)$. Supongamos que $L$ es el idioma aceptado por algún autómata finito $\mathcal{A}$. ¿Cómo encontrar los polinomios $P, Q$ dado $\mathcal{A}$? ¿Hay un procedimiento simple y una prueba?

Answer 1

Por favor, vea http://algo.inria.fr/flajolet/Publications/books.html, el libro Combinatorics analíticos primeros capítulos.