# Growth zeta-functions of regular languages

Dear All,

my following question may be known and ought to be known, so in case it is folklore please could you give me the references.

To start, it is obvious that growth of rational languages are always either polynomial or exponential. That is, if $L$ is a regular language, then the sequence $a_n$, where $a_n$ is the number of all words $w\in L$ of length $\leq n$, grows polynomially or exponentially.

But what I am really curious about is

$\textbf{Question}:$ If $L$ is a regular language, is then the correspondent growth zeta-function $\sum\limits_{n=1}^{\infty}a_nx^n$ rational?

-

Yes (though the standard term for these is generating functions rather than zeta functions); in fact, there's a relatively straightforward explicit construction for finding the generating function for a regular language given an unambiguous regular expression for it; replace null with $0$, any symbol with $x$, concatenation by multiplication, union with addition, and if $f(x)$ is the function for some expression $E$, then the function for $E^*$ is just $1\over 1-f(x)$. You should be able to convince yourself that this works by examining terms. On the other hand, not every rational function occurs as the generating function of a regular language. For details, you might have a look at http://www.morris.umn.edu/academic/math/Ma4901/Sp2011/Final/BrianGoslinga-final.pdf .