Generating function of regular set.

Question

Consider regular set of words $S$. Let $f_{S}(x) = \sum_{i = 0}^{\infty}a_{i}x^{i}$, where $a_{i}$ number of words with length $i$.

Prove that $f_{S}(x) = \frac{q(x)}{r(x)}$, where $q(x), r(x)$ are polynomials with integer coefficients.

I've deal with generating functions in sequences , but have no work with regular sets. Any idea?

Answer 1

You need to start with an unambiguous regular expression of your regular language that is, a regular expression that only makes use of unambiguous union, product and star. In more details, unambiguous union is disjoint union. A product $XY$ is unambiguous if every word $u$ of $XY$ has a unique decomposition of the form $u = xy$ with $x \in X$ and $y\in Y$. Finally, $X^*$ is an unambiguous star if $X$ is a code, that is, if $X^*$ is a free monoid of base $X$. In other words, every word $u$ of $X^*$ can be uniquely written as $x_1 \dots x_n$ for some $n \geqslant 0$ and $x_1, \dots, x_n \in X$.

One can show that every regular language admits an unambiguous regular expression. It is easy to compute such an expression using McNaughton-Yamada's algorithm, which can be found on this French but detailed Wikipedia entry. Once you have an unambiguous regular expression, to get the generation function, replace every letter by $t$ and use the conversion $s^* = 1/(1-s)$.

Here is an example. Start with the unambiguous regular expression $1 + (a^*b)^*aa^*$. Replacing $a$ and $b$ by $t$, you get the series $$ 1 +(t^*t)^*tt^* = 1 +\frac{1}{1-t^*t}tt^* = 1 + \frac{1}{1 - \frac{t}{1-t}}\frac{t}{1-t} = 1 + \frac{t}{1-2t} = \frac{1-t}{1-2t} $$ The Taylor expansion gives you the coefficients of the generating series. In Sage:

> t = var('t') 
> s = 1-t/(1-2*t) 
> taylor(s, t, 0, 8) 
> 128*t^8 + 64*t^7 + 32*t^6 + 16*t^5 + 8*t^4 + 4*t^3 + 2*t^2 + t + 1

You would obtain the same result by starting from the simpler unambiguous expression $1 + (a + b)^*a$.