Generating Function of a Regular Language

Question

It is well known that the generating function of a regular language $L$, i.e. $\sum n_kz^k$ where $n_k$ is the number of words of length $k$ in $L$, is rational, i.e. a quotient of two polynomials $P(z)/Q(z)$. Suppose that $L$ is the language accepted by some finite automaton $\mathcal{A}$. How to find the polynomials $P, Q$ given $\mathcal{A}$? Is there a simple procedure and proof?

Answer 1

Cannon does more than just refer to result that you ask for, he sketches the proof out. His proof is couched in the notation that he has set up for his application to hyperbolic groups. But it is easy enough to unravel the notation and express the proof in general.

Label the state set of the automaton as $0,\ldots,N$ where $0$ is the start state. Consider the transition matrix whose $i,j$ entry is the number of directed edges from $i$ to $j$ in the automaton. The growth function we want is the power series $f(x) = \sum n_k x^k$ where $n_k$ is the number of directed paths starting at $0$ of length $k$ and stopping at the terminal states of the automaton. For simplicity I'll assume every state is an terminal state; otherwise one just has to change the notation. With this assumption, $f(x) = f_0(x) + \ldots + f_N(x)$ where $f_i(x)$ is the growth function whose $k^{th}$ coefficient is the number of directed paths from state $0$ to state $i$ of length $k$. Cannon then writes a linear recursion for these functions: $f_0(x) = 1$ (the interpretation is that there are not actually any directed edges ending at the start state); and $$f_j(x) = x \cdot \sum_{i=0}^N b_{ij} \cdot f_i(x), j=0,\ldots,N $$ He explains how to express the coefficients $b_{ij}$ as functions of the entries of the transition matrix. Then he writes "It is a routine problem in linear algebra to solve (these equations) for $f_0, f_1, \ldots, f_N$ and $f$", which I interpret as rewriting the equations in vector form $F = x B F$ where $F$ is the column vector whose entries are the functions $f_0(x),\ldots,f_N(x)$ and $B=(b_{ij})$. So we get $(I - xB) F = (1;0;...;0)$ and this can be solved for $F$.