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.
Chomsky and Miller's seminal paper on regular languages @cite_21 does not address distances between regular languages. It uses Shannon's notion of channel capacity (equation 7 from @cite_21 ) for the entropy of a regular language: @math
@cite_21
2017473312
A finite state language is a finite or infinite set of strings (sentences) of symbols (words) generated by a finite set of rules (the grammar), where each rule specifies the state of the system in which it can be applied, the symbol which is generated, and the state of the system after the rule is applied. A number of equivalent descriptions of finite state languages are explored. A simple structural characterization theorem for finite state languages is established, based on the cyclical structure of the grammar. It is shown that the complement of any finite state language formed on a given vocabulary of symbols is also a finite state language, and that the union of any two finite state languages formed on a given vocabulary is a finite state language; i.e., the set of all finite state languages that can be formed on a given vocabulary is a Boolean algebra. Procedures for calculating the number of grammatical strings of any given length are also described.