2
$\begingroup$

I've been searching in the literature for examples of distances defined on the set of the DFAs (or on the set of minimal DFAs) that are defined on a given alphabet sigma.

Since the languages they describe (regular languages) can potentially have an infinite size, defining a distance is not a trivial matter.

Nevertheless, having a distance on these objects can be useful, in order to fit these in metric spaces, which allows for a range of things (in my case to assess the performance of an algorithm).

My only consistent idea so far is to create a distance similar to the edit-distance in labeled graphs on the minimized DFAs.

Does someone have ever heard of other distances ?

$\endgroup$
6
  • 2
    $\begingroup$ I haven’t, but I’d agree you’d have to define it on the set of minimal DFAs, or you risk comparing one worst-case automaton to a best-case automaton for two languages. $\endgroup$ Mar 27 '20 at 12:54
  • 5
    $\begingroup$ There are many ways to define a distance that is probably useless for most purposes. What did you have in mind for what you want to use the distance for, or what you want it to capture? That should probably influence the choice of distance. $\endgroup$
    – D.W.
    Mar 27 '20 at 16:24
  • $\begingroup$ @D.W. The kind of distance I'm looking for should reflect the distance between the languages recognized as much as possible. For instance, the problem with the edit-distance ont the minimal DFA is that it gives a greater distance between (a*) and (a+) than between (a*) and (b+). My use case is to assess performance on regular language inference algorithms by comparing the 'ground truth' DFA to the infered DFA. $\endgroup$
    – m.raynal
    Mar 28 '20 at 9:19
  • 1
    $\begingroup$ @m.raynal Not sure if it helps, but you can encode the language defined by DFA with an infinite binary sequence ($0$ stands for lack of the word, $1$ for presence) and then choose any metric for infinite sequences, for instance $\Sigma_{i}{\frac{|x_i - y_i|}{2^i}}$ $\endgroup$
    – Vladislav
    Mar 28 '20 at 17:33
  • 1
    $\begingroup$ But what do you mean by distance between languages? How do you want to use this distance metric? You say assess performance, but what aspect of performance? To ask it another way: How will you evaluate answers? We need criteria we can use to evaluate answers -- for instance, we need a way to vote on answers. This is not just for you, but also for others who might have a similar question. So, we need a well-defined question -- if you were hoping we would share as many ideas as we could think of and you'd pick one, I'm afraid this site isn't intended for brainstorming exercises. $\endgroup$
    – D.W.
    Mar 28 '20 at 17:37
3
$\begingroup$

There are many possible distance metrics, and without any criteria, we have no basis to choose. Here are two plausible ones.

Let $L_1,L_2$ be the languages of the two DFAs. Let $L$ be the symmetric difference of those languages (i.e., $(L_1 \setminus L_2) \cup (L_2 \setminus L_1)$).

One dissimilarity measure is $d(L_1,L_2) = 2^{-n}$ where $n=\min\{|x| : x \in L\}$, i.e., $n$ is the length of the shortest word in $L$. This is not a distance metric, because it does not satisfy the triangle inequality.

Another possibility is to use the density of $L$, i.e.,

$$d(L_1,L_2) = \sum_{n=0}^\infty {|L \cap \Sigma^n| \over 2^n |\Sigma|^n}.$$

This one is a distance metric.

These can be computed given DFAs for $L_1,L_2$. You can easily compute a DFA for $L$. Then, it is easy to find the length of the shortest word in $L$ using breadth-first search.

Computing the density is a bit trickier, but can be done efficiently using a little more math. Let $A$ denote the transition matrix of the DFA for $L$, i.e., $A_{ij}=1$ if there is a transition (on any input symbol) from state $i$ to state $j$, or $A_{ij}=0$ if not. Let $s$ denote the one-hot vector indicating the start state, i.e., $s_i=1$ iff $i$ is the start state, and $f$ denote the one-hot vector indicating the final states, i.e., $f_i=1$ iff $i$ is an accepting state. Now $|L \cap \Sigma^n| = s^\top A^n f$, so the distance is given by

$$d(L_1,L_2) = \sum_{n=0}^\infty {s^\top A^n f \over 2^n |\Sigma|^n} = s^\top C f$$

where

$$C = \sum_{n=0}^\infty B^n = {1 \over I - B} = (I - B)^{-1}$$

where $B={1 \over 2|\Sigma} A$ and $I$ represents the identity matrix. This can be computed in time proportional to the cube of the number of states in the DFA for $L$ using standard algorithms for matrix inversion.

$\endgroup$
0
$\begingroup$

I finally found in the literature a paper answering my question precisely, as well as providing a framework to define distances between languages.

The method is very similar to the one explained by @D.W in his answer (it is based on defining a distance by computing a density on the symmetric difference), it only provides a slightly more formal and more general framework, and also provides several examples of possible metrics.

The paper can be found here, it is 'Approximate Language Identification' by R.M. Wharton (1974).
It is one of the founding papers for grammatical inference of languages though probabilistic language models.

$\endgroup$

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.