7
$\begingroup$

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 !

$\endgroup$
  • $\begingroup$ If language density is not interesting to you, I suggest not studying it. $\endgroup$ – Yuval Filmus Mar 5 at 11:13
  • 2
    $\begingroup$ @YuvalFilmus Well, sure, but it can be hard to know how interesting something is without knowing what you can do with it. Hence the question (and your answer). $\endgroup$ – David Richerby Mar 5 at 18:42
6
$\begingroup$

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

  1. The density of $(1+01)^*$ is the Fibonacci sequence.
  2. The density of a regular unary language is eventually periodic.
  3. 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.

$\endgroup$
4
$\begingroup$

$E_L(n)$ describes how many bits of information you get from a string of length $n$, assuming it belongs to the language.

For many languages the function would be a rather smooth function in $n$. There are of course languages where the language only contains strings of even length, for example, in which case $E_L(n)$ isn't even defined for odd $n$.

$E_L(n)$ together with the logarithm of $|\Sigma|$ tells you how likely it is that a random string is in $L$. Usually people try to create strings in a language (that's what programmers usually do), and a low entropy means small mistakes are more likely to get caught.

Which is a good thing, because usually a string in the language $L$ has some semantics, and when I wanted to create a string that is supposed to be in L and has semantics $X$, and a make a small mistake using one or two wrong symbols, I want to be told that my string is not in $L$, and not produce end up with a string in $L$ with the wrong semantics.

If a language has very high entropy, so that most random strings are in $L$ (but with probably very different derivations), it is very hard to find errors because anything could be in $L$.

$\endgroup$
4
$\begingroup$

Density is what you get when you want a measure for the size of infinite languages. We can't quantify that by just taking their number of elements, which is the same for all infinite languages: (enumerable) infinity.

Still, we have an intuition about the relative sizes of infinite languages. For instance, about the language of all even strings over a given alphabet, we say it contains half of all strings over that alphabet, so intuitively, the former is half the size of the latter. Similarly, we can say that whenever $L_1 = L_2 \cup L_3$, the size of $L_1$ is at least that of $L_2$ and the size of $L_3$, and it is their sum when $L_2$ and $L_3$ are disjoint.

We want a notion of size for which this holds even for infinite languages. The answer is to consider size not as equal to the total number of strings in the language, but as the proportion of strings of each length that is in the language:

$ \displaystyle \delta(L) \mathrel{\mathop{=}\limits_{\scriptsize D}} \sum_{n \in \mathbb{N}}\frac{ | \{ w \in L \mid |w| = n \} | }{ | \{ w \in \Sigma^* \mid |w| = n \} | } = \sum_{n \in \mathbb{N}}\frac{ p_{\scriptsize L}(n) } { 2^{|\Sigma^*|} } $

but the density function $p_{\scriptsize L}$ grows exponentially, like the denominator, so we may wish to use the proportions of their logarithms instead:

$ \displaystyle \delta'(L) \mathrel{\mathop{=}\limits_{\scriptsize D}} \sum_{n \in \mathbb{N}}\frac{ \mathbb{log}\, p_{\scriptsize L}(n) } { \mathbb{log}\, 2^{|\Sigma^*|} } = \frac{1}{ |\Sigma^*| } \sum_{n \in \mathbb{N}} \mathbb{log}\, p_{\scriptsize L}(n) $

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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