What is language density used for?

If we have a langage $L$ over an alphabet $\Sigma$, then we can defined the density function of $L$ as :


$$ p_L(n) = | L \cap \Sigma^n | $$

I am wondering why it’s useful to study this function and what informations it gives on $L$.

Moreover, we can then defined the entropy of $L$ as :

$$E_L(n) = \frac{1}{n} \log p_L(n) $$

Once again I am wondering what information does this function reveal about $L$. Moreover, is there any way to think intuitively what the entropy of a language really represents?

Thanks you !

The number of words of given length in a language is a very natural parameter. Here are some examples to pique your interest:

• The density of $(1+01)^*$ is the Fibonacci sequence.

• The density of a regular unary language is eventually periodic.

• The density of a regular language is of the form $\Theta(n^k \lambda^n)$ for some integer $k \geq 0$ and real $\lambda \geq 0$.

The parameter $E_L(n)$ measures the entropy per character of a random word of length $n$ in $L$, chosen uniformly at random. For example, if $L$ consists of all binary words containing $\lfloor pn \rfloor$ ones (where $n$ is the length of the words), then $E_L(n)$ converges to $h(p)$, the binary entropy function.

StackExchange Computer Science Q#105162, answer score: 6