# Is there a metric or distance of two languages?

Given a language $$L$$, I am finding a method to evaluate the advantage of an automaton to decide $$L$$.

My goal is to decide a language $$L$$ (and maybe it is not decidable for automata). If one constructs an automaton $$A_{1}$$ whose laguage is $$L_{1}$$, I want to know the advantage of $$A_{1}$$ for decisidng $$L$$. If there is a distance or metric of two languages $$d(\cdot, \cdot)$$, I can define $$\mathrm{Adv}_{L}(A_{1}) = d(L_{1}, L)$$. Thus, we can say $$A_{1}$$ is better than $$A_{2}$$ respect of $$L$$ if $$\mathrm{Adv}_{L}(A_{1}) > \mathrm{Adv}_{L}(A_{2})$$.

In my opinion, the follow conditions are satisfied at least.

1 It is non-negativity and identity of indiscernibles, $$d(L_{1}, L_{2}) \geq 0 ~\text{iff}~L_{1} = L_{2}$$.

2 It is symmetry, $$d(L_{1}, L_{2}) = d(L_{2}, L_{1})$$.

3 If $$L_{1} \cap L \subseteq L_{2} \cap L$$ and $$L_{1} \setminus L = L_{2} \setminus L$$, then $$d(L,L_{1}) \leq d(L,L_{2})$$.

4 If $$L_{1} \cap L = L_{2} \cap L$$ and $$L_{1} \setminus L \subseteq L_{2} \setminus L$$, then $$d(L,L_{1}) \geq d(L,L_{2})$$.

Note that I am not sure the condition 3 and condition 4 above is suitful.

Follows may be helpful.

How similar are two DFAs? -not just binary equivalence-

Measures and probability in formal language theory

• You can take density of the symmetric difference, for various notions of density. – Yuval Filmus Aug 5 at 5:06
• @ Yuval Filmus, the problem is that the language is infinite. I have no idea to define a proper density. – TeamBright Aug 5 at 7:08
• @TeamBright: That's what density is for. See e.g. What is language density used for? – reinierpost Aug 5 at 17:32
• Another popular notion of density is Schnirelmann density. – Yuval Filmus Aug 5 at 17:41
• @TeamBright Did you miss the triangle inequality? The triangle inequality is the most distinguishing quality when we are defining a metric in general. – Apass.Jack Aug 6 at 17:03