MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).
3

let $\sum_0^n l_i x^i$ and $\sum_0^n 2^i x^i$ be generating function of L a given language and the closure over alphabet $\Sigma= \{0,1 \}$ when $n\to\infty$. let$$D=\frac{\sum_0^n l_i }{\sum_0^n 2^i }$$,$$d=\frac{ l_i x^i}{ 2^i x^i}=\frac{ l_i }{ 2^i }$$.

Obviously,$0 \leq D,d \leq 1$.when(under what condition such as the class of the language or language with what feature) does $lim_{n\to \infty} D$ and $lim_{n\to \infty} d$ exist?

If the limit does not exist,how does the $D,d$ vibrates or how about the $f(D,n)$ and $f(d,n)$ relating to class of language or feature of language?

Any result of questions above?

flag

1 Answer

1

I suggest looking at Jean Berstel, Sur la densité asymptotique de langages formels. (French) Automata, languages and programming (Proc. Sympos., Rocquencourt, 1972), pp. 345–358. North-Holland, Amsterdam, 1973.

link|flag
@Benjamin,Thank you so much,it is French again,I have to learn a new language for several topics. – XL Sep 20 at 13:01

Your Answer

Get an OpenID
or

Not the answer you're looking for? Browse other questions tagged or ask your own question.