An undecidable problem for context-free grammars
From MaRDI portal
This note deals with the following problem: Let \(G=(V,\Sigma,P,S)\) be a context-free grammar and let \(h: \Sigma\) \({}^*\to \Sigma^*_ 1\) be a homomorphism. Are there distinct words v and w in L(G) such that \(h(v)=h(w)?\) It is shown that the problem is undecidable by reducing the ambiguity problem for context-free grammars to it.
Recommendations
- scientific article; zbMATH DE number 3845565
- A uniform framework for problems on context-free grammars
- Context-freeness of parsing expression languages is undecidable
- A context-free language decision problem
- The Unsolvability of the Recognition of Linear Context-Free Languages
- (Un)decidability of the emptiness problem for multi-dimensional context-free grammars
- Decidability problems in grammar systems
- Context-freeness of the power of context-free languages is undecidable
- scientific article; zbMATH DE number 3932414
- Algorithmic decidability of restricted ambiguity in context-free grammars
Cites work
Cited in
(12)- The undecidability of form equivalence for context-free and EOL forms
- Decidability problems in grammar systems
- Efficient coding of formalized messages
- Context-freeness of the power of context-free languages is undecidable
- Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth
- Injectivity of the quotient h g of two morphisms and ambiguity of linear grammars
- scientific article; zbMATH DE number 1346367 (Why is no real title available?)
- scientific article; zbMATH DE number 938665 (Why is no real title available?)
- Context-freeness of parsing expression languages is undecidable
- The inherent ambiguity partial algorithm problem for context free languages
- Automata, Languages and Programming
- A note on ambiguity in context-free grammars
This page was built for publication: An undecidable problem for context-free grammars
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1067789)
