On the Density of Regular Languages

• Autorzy: Koga, Toshihiro
• Języki publikacji: EN

Abstrakty

EN

Let ∑ be an alphabet which has at least two symbols. The density of L ⊆ ∑* is defined as D(L) := lim_n |L ∩ ∑ⁿ|/|∑ⁿ| ∈ [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.

Słowa kluczowe

EN

formal languages; regular languages; density

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2019
• Tom: Vol. 168, nr 1
• Strony: 45--49
• Opis fizyczny: Bibliogr. 4 poz.

Twórcy

autor

Koga, Toshihiro

• #D-804 Purimasitei 4-1-1, Nagatsutaminamidai, Midori-ku, Yokohama-shi, Kanagawa-ken 226-0018 Japan,

Bibliografia

• [1] Sin’ya R. An Automata Theoretic Approach to the Zero-One Law for Regular Languages: Algorithmic and Logical Aspects. In: Proceedings Sixth International Symposium on Games, Automata, Logics and Formal Verification, GandALF 2015, Genoa, Italy, 21-22nd September 2015. 2015 pp. 172-185. doi:10.4204/EPTCS.193.13.
• [2] Sin’ya R. Zero-One Law for Regular Languages. Ph.D. thesis, Tokyo Institute of Technology, 2016-03. URL http://id.nii.ac.jp/0083/00230141.
• [3] Eilenberg S, Tilson B. Automata, Languages, and Machines. Academic Press, 1976. ISBN-10:0122340027, 13:978-0122340024.
• [4] Linz P. An introduction to formal languages and automata. Jones & Bartlett Publishers, 2011. ISBN-10:144961552X, 13:978-1449615529.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).

Identyfikatory

DOI

10.3233/FI-2019-1823