Welcome to MathOverflow

Question

3

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

flag	asked Apr 16 2010 at 17:11 Łukasz Grabowski 2,771●5●16

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 2010 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 2010 at 2:36

Dylan: can you give a reference for that? – Łukasz Grabowski Apr 17 2010 at 15:20

Stanley, Enumerative Combinatorics, Vol. II, Theorem 6.5.7. – Qiaochu Yuan Apr 28 2010 at 7:15

Dylan Thurston · Answer 1 · 2010-04-28 06:46:49Z UTC

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

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

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.