[Solved]: Measures and probability in formal language theory

Problem Detail: 

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)?

Asked By : Cornelius Brand

Answered By : Raphael

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/13631

3.2K people like this

 Download Related Notes/Documents