Abstract:
A metric framework for regular languages and
ω-regular languages is proposed to facilitate their quantitative analysis. By introducing the notion of distance from metric theory, a quantitative relationship between languages and automata is established, enabling the acceptance behavior of an automaton with respect to a given language to be quantified. Based on the concept of pseudometrics, approximate regular and approximate
ω-regular languages are defined while preserving as many desirable properties of classical regular and
ω-regular languages as possible. Furthermore, the notion of distance is generalized, and a distance threshold
α is introduced into the classical Büchi automaton framework, thereby quantifying the language acceptance conditions. Finally, an automata-theoretic characterization of the proposed approximate
ω-regular languages is established.