Context-freeness of parsing expression languages is undecidable

DOI10.1142/S0129054118500296MaRDI QIDQ5384531zbMATH OpenOpenAlexWikidataFDO

Authors Toshihiro Koga

Publication date 24 June 2019

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0129054118500296

zbMATH Keywords

context-free grammarsformal languagesparsing expression grammarsundecidable problems

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42) Formal languages and automata (68Q45)

Recommendations

• Context-freeness of the power of context-free languages is undecidable
• An undecidable problem for context-free grammars
• HOLONOMIC GENERATING FUNCTIONS AND CONTEXT FREE LANGUAGES
• scientific article; zbMATH DE number 1067868
• A note on ambiguity in context-free grammars

Cites work

• A note on undecidable properties of formal languages
• scientific article; zbMATH DE number 3776895 (Why is no real title available?)
• scientific article; zbMATH DE number 1517989 (Why is no real title available?)
• Linear parsing expression grammars
• Parsing expression grammars: a recognition-based syntactic foundation

Cited in

(3)

• An undecidable problem for context-free grammars
• Context-freeness of the power of context-free languages is undecidable
• Computing the Shortest String and the Edit-Distance for Parsing Expression Languages

This page was built for publication: Context-freeness of parsing expression languages is undecidable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5384531)