An undecidable property of context-free languages
Zoltán Ésik · arXiv (Cornell University) · 2010
We prove that there exists no algorithm to decide whether the language generated by a context-free grammar is dense with respect to the lexicographic ordering. As a corollary to this result, we show that it is undecidable whether the lexicographic orderings of the languages generated by two context-free grammars have the same order type.