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

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

<p>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.)  </p>

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

<p>Jean-Eric Pin has written a survey article, <a href="http://hal.inria.fr/docs/00/35/96/77/PDF/03-pin.pdf"><em>Profinite Methods in Automata Theory</em></a>, in which he surveys some more general metrics, and also draws some connections to Stone duality. </p>

CC BY-SA 3.0
2013-06-03T14:02:43.983Z
Thanks, I was aware of Cantor metric, but not of its use for defining the Hausdorff metric, this seems perfectly fine.
Denis
CC BY-SA 3.0
2013-06-03T13:58:10.640Z
2013-06-03T13:58:10.640Z
Neel Krishnaswami
<p>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.</p>

<p>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).</p>

<p>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.</p>

<p>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.</p>

<reference-request><fl.formal-languages><regular-language>
Distance between regular languages
Denis
# Distance between regular languages

(Asked by: username_0 on 2013-06-03)

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.

**Tags:** reference-request, fl.formal-languages, regular-language

---

## 1 answers

### Answer by username_1 on 2013-06-03. Score: 12 | Accepted answer

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*](http://hal.inria.fr/docs/00/35/96/77/PDF/03-pin.pdf), in which he surveys some more general metrics, and also draws some connections to Stone duality.

> **Comments:**
> **username_0**: Thanks, I was aware of Cantor metric, but not of its use for defining the Hausdorff metric, this seems perfectly fine.  

---

