# Measures and probability in formal language theory

I am looking for references for the following problem: I have a very special class of regular languages and my aim is to express (and to justify my conjecture) that this class itself is very small in some way (as a subset of the regular languages) and that the languages contained in this class are rather "bloated".

For the latter point, I could prove that all languages in the class have a large diameter with respect to many common metrics on strings. However, I want to consider the following: Given a language from the class, we know it has a large diameter, but does it also have a large "volume" (that is, measure), or put differently, if I choose randomly a finite word, is there anything meaningful to say about how "probable" it is that the word belongs to the language? Of course, we can lift the problem: Picking a random language, how probable is it to get a language in the class?

Are there any references or standard approaches for looking at classes of (regular) languages from this point of view (or is this considered as generally uninteresting)?

• I don't understand what you mean by "diameter", but it's not relevant to your question, isn't it? – Raphael Aug 7 '13 at 7:18
• @Raphael: No, it really isn't, but for completeness, it refers to the standard notion of the diameter of a set in metric spaces, i.e. the supremum of the set of distances between any two elements from the set. – Cornelius Brand Aug 7 '13 at 8:55
• Won't this be $\infty$ on all infinite languages? At least, it should be like that on all metrics I know, e.g. $\operatorname{dist}(a, a^n)$ will go to infinity with $n$. – Raphael Aug 7 '13 at 11:30
• First of all, technically, not all metrics are unbounded. Apart from that, if you define a metric $d$ on words like in cstheory.stackexchange.com/questions/17881/… by $d(u,v):=2^{-k}$ where $k$ is the first position the two strings $u$ and $v$ differ, then not all infinite languages have diameter $\infty$. For instance, take $L_n:=\{a^k | k \geq n\}$, we have that diam ${L_n} \rightarrow 0$ as $n \rightarrow \infty$ with respect to that metric. – Cornelius Brand Aug 7 '13 at 11:47
• I see, I was not aware of this/such metric(s). – Raphael Aug 7 '13 at 11:52

There is the concept of density of languages (see e.g. here). The density $\operatorname{den}_L : \mathbb{N} \to [0,1]$ of $L \subseteq \Sigma^*$ is defined by

$\qquad \operatorname{den}_L(n) = \frac{|L \cap \Sigma^n|}{|\Sigma^n|}$.

For any fixed length, the density corresponds to the probability of picking a word from the language, assuming we pick uniformly at random. Add a distribution over lengths and you may have what you need.

You may be able to express your concept of "volume" in terms of this notion, maybe by investigating $\lim_{n \to \infty} \operatorname{den}_L(n)$.

As for "randomly picking a language" -- how would you do that? There are uncountably many languages over any given alphabet so I'm not sure how you would define a (nice) probability distribution.

• As far as density is concerned, this seems very useful and I think this comes as close to what I was looking for as it gets. As for "randomly picking a language", I am aware that this (speaking of probability) is rather naive and not appropriate from a mathematical point of view, which is why I was also asking for general measures (something that is as canonical for the space of formal languages as the Lebesgue measure is for $\mathbb{R}^n$). – Cornelius Brand Aug 7 '13 at 9:09

I don't know any standard measures, but here is an idea regarding your first question. It is known that the number of words of length $n$ in a regular language is $Cn^t \alpha^n (1 + o(1))$ for some integer $t \geq 0$ and reals $C,\alpha \geq 0$ (more accurately, for some integers $d,N \geq 1$ this is true for every residue class modulo $d$, given $n \geq N$). You could find the parameters $C,t,\alpha$ and using them argue that your language is "dense".

• This seems quite relevant. Do you have references concerning the parameters themselves (or some names or keywords I could look up) and how to find them in some special cases (to get an idea how to approach the problem)? – Cornelius Brand Aug 6 '13 at 20:41
• Wikipedia has some references: en.wikipedia.org/wiki/…. – Yuval Filmus Aug 6 '13 at 21:16