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

Answer 2

Please see http://algo.inria.fr/flajolet/Publications/books.html ,the book Analytic combinatorics's first several chapters.

Answer 3

This is of course a special case of the Chomsky-Schutzenberger theorem that unambiguous context-free languages have algebraic generating functions. Restricted to a regular language it is like this. Assume the automata has state set $1,...,n$. Let $1$ be the initial state for convenience. Let A be the adjacency matrix of the automaton, let $e_1$ be the standard unit row vector and let $c$ be the column vector which is the characteristic vector of the terminal states. Then it is easy to see that the generating function is $$f(t)=\sum_{n=0}^{\infty}e_1A^nct^n = e_1\left[\sum_{n=0}^{\infty}A^nt^n\right]c= e_1(I-tA)^{-1}c.$$ Now using the classical adjoint formula for the inverse, you get that the denominator is $\det(I-tA)$ and the numerator is what it is.

Answer 4

Start by making a deterministic finite automaton $M$. Now $n_k$ is the number of walks of length $k$ from the starting state to an accepting state, so $\sum n_k z^k$ is the sum of some entries of $(I-zA)^{-1}$, where $A=(a_{ij})$ is the integer matrix in which $a_{ij}$ is the number of transitions from state $i$ to state $j$. The entries you need to add are the $(k,\ell)$ entries where $k$ is the starting state and $\ell$ is an accepting state. To get this as a rational function, write $(I-zA)^{-1}$ using Cramer's rule. The denominator (before cancelling of any common factors) is the determinant $|I-zA|$. The numerator is the adjugate of $I-zA$, whose entries are cofactors, which are also determinants. So in total, if there are $m$ accepting states, you get a sum of $m$ determinants divided by one determinant, and all these determinants are polynomials in $z$.

Answer 5

This is basically equivalent for finding an unambiguous regular expression for the language. This MO answer explains how to do it, given an DFA $\mathcal A$.

The rest is easy:

• replace $\emptyset$ by $0$
• replace $\epsilon$ by $1$
• replace any symbol with $x$
• replace concatenation with multiplication
• replace $\cup$ with $+$
• replace Kleene star with $1/1-f(x)$.

Source: this paper.