Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer

up vote 6 down vote accepted

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 .

share|improve this answer
1  
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. –  Victor Jun 21 '11 at 20:21
    
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/… –  Sam Nead May 31 '13 at 12:11
    
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. –  Sam Nead May 31 '13 at 12:15
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.