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.
Several works since Chomsky and Miller have used this same of length exactly @math formula to define the entropy of a regular language @cite_14 @cite_13 @cite_11 . These works define entropy as Chomsky and Miller, but add the caveat that they use the upper limit when the limit does not exist. There is even a paper on non-regular languages that uses the same entropy definition @cite_13 . Here we provide foundation for those works by showing the upper limit to be correct (Theorem ). Further, this paper suggests an equivalent expression for entropy that may be considered more elegant: it is a limit that exists as a finite number for all regular languages.
@cite_14 @cite_13 @cite_11
1998314653 2035875679
We use an information-theoretic notion, namely, (Shannon) information rate, to generalize common syntactic similarity metrics (like Hamming distance and longest common subsequences) between strings to ones between languages. We show that the similarity metrics between two regular languages are computable. We further study self-similarity of a regular language under various similarity metrics. As far as semantic similarity is concerned, we study the amplitude of an automaton, which intuitively characterizes how much a typical execution of the automaton fluctuates. Finally, we investigate, through experiments, how to measure similarity between two real-world programs using Lempel-Ziv compression on the runs at the assembly level. Let L be an irreducible regular language. Let W be a non-empty set of words (or sub-words) of L and denote by LW = v ∈ L:w ⊏ v, ∀w ∈ W the language obtained from L by forbidding all the words w in W. Then the entropy decreases strictly: ent(LW) < ent(L). In this note we present a new proof of this fact, based on a method of Gromov, which avoids the Perron-Frobenius theory. This result applies to the regular languages of finitely generated free groups and an additional application is presented.