DMTCS Proceedings, Computational Logic and Applications, CLA '05

Font Size:  Small  Medium  Large

Undecidable problems concerning densities of languages

Jakub Kozik

Abstract


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 ∈ ℕ ).

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page

Valid XHTML 1.0 Transitional