A definition of measures over language space

摘要

As an attempt to associate a real number with a language, entropies of languages are computed by Banerji, Kuich, and others. As mappings from languages to real numbers, in this paper, measures over languages are presented. These measures satisfy additivity while entropies do not. Two kinds of measures, p-measure and ω-measure, are defined, and the computing method of these measures is shown for regular languages and context-free languages. Some properties of these measures are applied to show the nonregularity of several languages.