6
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
9
$\begingroup$

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 .

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Thanks, it's actually so obvious now indeed that the correspondent power series is rational. I should have given a normal proper thought about the question. $\endgroup$
    – Victor
    Commented Jun 21, 2011 at 20:21
  • $\begingroup$ I've deleted my previous comments, after pulling all of the interesting material here. For anybody reading this: there is a delicate point residing in the phrase "unambiguous regular expression". If you are given the language via a regular expression, then the process of disambiguation goes via constructing a deterministic FSA for the language. For a how-to, see: mathoverflow.net/questions/45149/… $\endgroup$
    – Sam Nead
    Commented May 31, 2013 at 12:11
  • $\begingroup$ The tricky part is that the deterministic FSA may be exponentially larger than the given regular expression! Disambiguation is also supposedly dealt with in Volume A, Chapter 8 of "Automata, languages, and machines" by Samuel Eilenberg. I found this reference somewhat cryptic. $\endgroup$
    – Sam Nead
    Commented May 31, 2013 at 12:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .