3
$\begingroup$

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

Improve this question
$\endgroup$
4
  • 5
    $\begingroup$ 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... $\endgroup$
    – Qiaochu Yuan
    Commented Apr 16, 2010 at 17:22
  • 2
    $\begingroup$ 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. $\endgroup$
    – Dylan Thurston
    Commented Apr 17, 2010 at 2:36
  • $\begingroup$ Dylan: can you give a reference for that? $\endgroup$
    – Łukasz Grabowski
    Commented Apr 17, 2010 at 15:20
  • $\begingroup$ Stanley, Enumerative Combinatorics, Vol. II, Theorem 6.5.7. $\endgroup$
    – Qiaochu Yuan
    Commented Apr 28, 2010 at 7:15

1 Answer 1

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ I think you're talking about the Kleene-Schützenberger Theorem. $\endgroup$
    – François G. Dorais
    Commented Apr 28, 2010 at 8:53
  • $\begingroup$ 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. $\endgroup$
    – Dylan Thurston
    Commented Apr 28, 2010 at 16:46

You must log in to answer this question.

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