DOAJ Open Access 2005

Undecidable problems concerning densities of languages

Jakub Kozik

Lihat Sumber DOI

Abstrak

In this paper we prove that the question whether a language presented by a context free grammar has density, is undecidable. Moreover we show that there is no algorithm which, given two unambiguous context free grammars on input, decides whether the language defined by the first grammar has a relative density in the language defined by the second one. Our techniques can be extended to show that this problem is undecidable even for languages given by grammars from $LL(k)$ (for sufficiently large fixed $k ∈ \mathbb{N} )$.

Topik & Kata Kunci

Mathematics

Penulis (1)

Jakub Kozik

Format Sitasi

APA MLA BibTeX

Kozik, J. (2005). Undecidable problems concerning densities of languages. https://doi.org/10.46298/dmtcs.3471

Akses Cepat

Lihat di Sumber doi.org/10.46298/dmtcs.3471

Informasi Jurnal

Tahun Terbit: 2005
Sumber Database: DOAJ
DOI: 10.46298/dmtcs.3471
Akses: Open Access ✓