arXiv Open Access 2020

Asymptotic Approximation by Regular Languages

Ryoma Sin'ya

Lihat Sumber

Abstrak

This paper investigates a new property of formal languages called REG-measurability where REG is the class of regular languages. Intuitively, a language \(L\) is REG-measurable if there exists an infinite sequence of regular languages that "converges" to \(L\). A language without REG-measurability has a complex shape in some sense so that it can not be (asymptotically) approximated by regular languages. We show that several context-free languages are REG-measurable (including languages with transcendental generating function and transcendental density, in particular), while a certain simple deterministic context-free language and the set of primitive words are REG-immeasurable in a strong sense.

Topik & Kata Kunci

cs.FL

Penulis (1)

Ryoma Sin'ya

Format Sitasi

APA MLA BibTeX

Sin'ya, R. (2020). Asymptotic Approximation by Regular Languages. https://arxiv.org/abs/2008.01413

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2020
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓