An undecidable problem for context-free grammars (Q1067789)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | An undecidable problem for context-free grammars |
scientific article |
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
