Distance between regular languages

Question

I want to define a notion of "closeness" between two regular languages of finite words in $\Sigma^*$ (and/or infinite words in $\Sigma^\omega$). The basic idea is that we want two languages to be close if they don't differ by many words. We could also use the edit distance in some way... I could not find good references on this issue.

I don't call it a distance because I don't require all the distance axioms to be true (although it's not bad if they are).

A first attempt is to define $$d(L,K)= \limsup_{n\to\infty} \frac{|L_n\Delta K_n|}{|L_n\cup K_n|}$$ where $L_n$ and $K_n$ are the restrictions of $L$ and $K$ to $\Sigma^n$, and $\Delta$ is the symmetric difference.

Is this "distance" studied? Are there references on the subject (possibly with alternative choices for distance function)? Any help or pointer would be appreciated, thanks.

Answer 1

As you perhaps already know, a common metric on words is the Cantor metric, which is defined as:

$$ d(l, k) = \left\{ \begin{array}{ll} 0 & \mbox{if } l = k \\ 2^{-n} & \mbox{where } n = \min\{i\in\mathbb{N} \;|\;l_i \not=k_i\} \end{array} \right. $$

Roughly speaking, if a string is a sequence of events, the distance between two strings is $2^{-n}$, where $n$ is the first time they differ. This can be lifted to a metric on (nonempty) languages by using the Hausdorff metric. (If you allow infinite strings, you also have to ensure that the languages are Cauchy-complete.)

This metric shows up a lot in verification. The first reference to this that I know is Alpern and Schneider 1985, Defining Liveness. (Sorry for the absence of a link, but I couldn't find an online copy.)

Jean-Eric Pin has written a survey article, Profinite Methods in Automata Theory, in which he surveys some more general metrics, and also draws some connections to Stone duality.