An undecidable property of context-free languages
classification
💻 cs.FL
cs.DM
keywords
context-freegeneratedlanguageslexicographicundecidablewhetheralgorithmcorollary
read the original abstract
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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.