density of formal language？ - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T22:02:36Z http://mathoverflow.net/feeds/question/71124 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/71124/density-of-formal-language density of formal language？ XL 2011-07-24T12:48:55Z 2012-09-19T02:00:24Z <p>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 }$$.</p> <p>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?</p> <p>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?</p> <p>Any result of questions above?</p> http://mathoverflow.net/questions/71124/density-of-formal-language/107525#107525 Answer by Benjamin Steinberg for density of formal language？ Benjamin Steinberg 2012-09-19T02:00:24Z 2012-09-19T02:00:24Z <p>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. </p>