# characterization of regular languages among (say) those computable in linear time

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,...)?

-
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
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

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.)

-
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