An undecidable problem for context-free grammars (Q1067789)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: An undecidable problem for context-free grammars |
scientific article; zbMATH DE number 3930364
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | An undecidable problem for context-free grammars |
scientific article; zbMATH DE number 3930364 |
Statements
An undecidable problem for context-free grammars (English)
0 references
1985
0 references
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.
0 references
undecidability
0 references
left Szilard language
0 references
ambiguity
0 references
0.89707816
0 references
0.8952961
0 references
0.8943292
0 references
0.8913181
0 references
0 references
0.8890152
0 references
0.8879512
0 references
