On the Density of Regular Languages

Article type: Research Article

Authors: Koga, Toshihiro^{; *}

Affiliations: #D-804 Purimasitei 4-1-1, Nagatsutaminamidai, Midori-ku, Yokohama-shi, Kanagawa-ken 226-0018 Japan. [email protected]

Correspondence: [*] Address for correspondence: #D-804 Purimasitei 4-1-1, Nagatsutaminamidai, Midori-ku, Yokohama-shi, Kanagawa-ken 226-0018 Japan.

Abstract: Let ∑ be an alphabet which has at least two symbols. The density of L ⊆ ∑* is defined as D(L) := limn |L ∩ ∑n|/|∑n| ∈ [0, 1], provided that the limit exists. In 2015, R. Sin’ya has discovered an interesting relation between regular languages and their densities: If L ⊆ ∑* is a regular language, then D(L) = 0 if and only if there exists s ∈ ∑* such that ∑*s∑* ∩ L = ø. In this paper, we give a simple proof of this theorem, obtaining it as a simple consequence of the pumping lemma for regular languages.

Keywords: Formal languages, Regular languages, Density

DOI: 10.3233/FI-2019-1823

Journal: Fundamenta Informaticae, vol. 168, no. 1, pp. 45-49, 2019