coefficients of counting series

41 Views Asked by At

Given a language, the generating series is $f(x)=\sum_1^{\infty}a_i x^i$ where $i$ is the length of words and $a_i$ is the number of words with length $i$, if the language is c.e, is the sequence$a_1,a_2,\dots,a_i,\dots$ decidable with input corresponding $i$?

And, given a language and it's grammar, the generating series is $f(x)=\sum_1^{\infty}a_i x^i$, if the language is c.e, is the sequence$a_1,a_2,\dots,a_i,\dots$ computable with input corresponding $i$?

What about computable language and grammar?

what about CFL and CFG?

1

There are 1 best solutions below

1
On

It is proved in [1, Corollary 2.2, p.50] that a series $\sum_{n \geqslant 0} a_nx_n$ in $\mathbb{Z}[[x]]$ is the generating function of some regular language if and only if it is a rational series over the semiring $\mathbb{N}$ and has constant term $0$ or $1$. In this case, the $a_n$ satisfy a linear recurrence relation and this series can be effectively computed given an automaton accepting the regular language.

The situation is already much harder for context-free languages. For instance, it is shown in [2] that if the generating function of a context-free language is transcendental, then this language is inherently ambiguous. Several such examples are given in [2], for instance $L=\{a^nbua^nv \mid n \geqslant 0 \text{ and } u, v \in \{a,b\}^*\}$.

[1] Berstel, Jean; Reutenauer, Christophe. Non-commutative Rational Series and Applications, Cambridge University Press, ISBN: 9780521190220, 2010

[2] Philippe Flajolet, Ambiguity and transcendence, Automata, languages and programming (Nafplion, 1985), LNCS 194, Springer, Berlin, 1985, 179-188.