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

For a given language A let A(n) denote the number of words in A of length smaller or equal to n. It is know that if A is a regular language then the function $ f(x) = \sum_{i=0}^\infty A(n)x^n$ is in fact a rational function.

Obviously there exist languages which are not regular but which have this property.

My question: does this property characterizes regular languages in any other, bigger, class of languages (computable in linear time, context-free,...)?

share|improve this question
5  
The language of palindromes over an alphabet of at least two letters is recognizable in linear time, context-free, and has rational generating function, but is not regular. So you're going to need a pretty severe restriction to exclude palindromes... –  Qiaochu Yuan Apr 16 '10 at 17:22
2  
On the other hand, if you can consider the sum of all the words in the language as an element in a non-commutative power series ring. That sum is rational iff the language is regular. –  Dylan Thurston Apr 17 '10 at 2:36
    
Dylan: can you give a reference for that? –  Łukasz Grabowski Apr 17 '10 at 15:20
    
Stanley, Enumerative Combinatorics, Vol. II, Theorem 6.5.7. –  Qiaochu Yuan Apr 28 '10 at 7:15
add comment

1 Answer

(Answering Lukasz's question from the comments)

If you consider the non-commutative power series for a language, the regular languages are characterized by having rational power series constructable with coefficients in $\mathbb{N}$. This is cited as Theorems 2.4 and 2.5 of

Koutschan, "Regular languages and their generating functions: The inverse problem", Theoretical Computer Science 391(1-2), pp. 65-74. 2008

who is quoting the obviously relevant book

Salomaa, Sittola, Bauer, and Gries, Automata-Theoretic Aspects of Formal Power Series, Springer-Verlag, 1978.

(However, I haven't yet read this last reference.)

share|improve this answer
1  
I think you're talking about the Kleene-Schützenberger Theorem. –  François G. Dorais Apr 28 '10 at 8:53
    
I didn't know that theorem by name; thanks. However, I was trying to characterize unweighted automata via their real-valued power series, which is somewhat more subtle than the statements I found of the Kleene-Schützenberger Theorem. –  Dylan Thurston Apr 28 '10 at 16:46
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.