This paper addresses the problem of determining the distance between two regular languages. It will show how to expand Jaccard distance, which works on finite sets, to potentially-infinite regular languages. The entropy of a regular language plays a large role in the extension. Much of the paper is spent investigating the entropy of a regular language. This includes addressing issues that have required previous authors to rely on the upper limit of Shannon's traditional formulation of entropy, because its limit does not always exist. The paper also includes proposing a new limit based formulation for the entropy of a regular language and proves that formulation to both exist and be equivalent to Shannon's original formulation (when it exists). Additionally, the proposed formulation is shown to equal an analogous but formally quite different notion of topological entropy from Symbolic Dynamics -- consequently also showing Shannon's original formulation to be equivalent to topological entropy. Surprisingly, the natural Jaccard-like entropy distance is trivial in most cases. Instead, the entropy sum distance metric is suggested, and shown to be granular in certain situations.
There is another proposal for the topological entropy of formal (including regular) languages that does not agree with the notions provided in this paper @cite_9 . That paper develops interesting formal results surrounding their definition of entropy, including showing it to be zero for all regular languages. Because their entropy is zero for all regular languages, it will not be helpful as a distance function for regular languages.
@cite_9
1900346975
We introduce the notion of topological entropy of a formal language as the topological entropy of the minimal topological automaton accepting it. Using a characterization of this notion in terms of approximations of the Myhill–Nerode congruence relation, we are able to compute the topological entropies of certain example languages. Those examples suggest that the notion of a “simple” formal language coincides with the language having zero entropy.