2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I don't understand what you mean by "diameter", but it's not relevant to your question, isn't it? $\endgroup$ – Raphael Aug 7 '13 at 7:18
  • $\begingroup$ @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. $\endgroup$ – Cornelius Brand Aug 7 '13 at 8:55
  • $\begingroup$ 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$. $\endgroup$ – Raphael Aug 7 '13 at 11:30
  • $\begingroup$ 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. $\endgroup$ – Cornelius Brand Aug 7 '13 at 11:47
  • $\begingroup$ I see, I was not aware of this/such metric(s). $\endgroup$ – Raphael Aug 7 '13 at 11:52
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$). $\endgroup$ – Cornelius Brand Aug 7 '13 at 9:09
2
$\begingroup$

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".

$\endgroup$
  • $\begingroup$ 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)? $\endgroup$ – Cornelius Brand Aug 6 '13 at 20:41
  • 2
    $\begingroup$ Wikipedia has some references: en.wikipedia.org/wiki/…. $\endgroup$ – Yuval Filmus Aug 6 '13 at 21:16

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.