1
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.