An undecidable property of context-free languages

2010/04/10 by Esik, Zoltan
#68Q42 #68Q45 #68Q55 #68Q70 #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)

paper · doi:10.48550/arxiv.1004.1736

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.

Related

• Scattered context-free linear orderings
• Context-free ordinals
• Detecting and Explaining (In-)equivalence of Context-Free Grammars
• On the complexity of the universality and inclusion problems for unambiguous context-free grammars (technical report)
• Pumping lemma and Ogden lemma for displacement context-free grammars