undecidability of CFG ambiguity
A grammar is AMBIGUOUS if some string in its language has two different parse trees — two genuinely different ways to build it. Ambiguity is bad news for compilers, since it means a sentence has more than one structural meaning. So a natural wish is a tool that takes any grammar and reports 'ambiguous' or 'unambiguous'. That tool cannot exist: deciding whether a context-free grammar is ambiguous is UNDECIDABLE.
Be careful what is and is not claimed. For a SPECIFIC string, you can list all its parse trees (there are finitely many, found by parsing) and see if there are two — that is decidable. What is undecidable is the GRAMMAR-WIDE question: is there ANY string, among infinitely many, that has two parse trees? No algorithm settles that for every grammar. The proof reduces from the Post correspondence problem: from any PCP instance one constructs a grammar that is ambiguous if and only if the PCP instance has a solution; since PCP is undecidable, ambiguity must be too.
Two honest caveats sharpen the picture. First, ambiguity is a property of a GRAMMAR, not of a language: the same language can have an ambiguous grammar and an unambiguous one. Second — and worse — some context-free languages are INHERENTLY ambiguous, meaning every grammar for them is ambiguous; for those, no rewriting can save you. Because ambiguity is undecidable, parser-generator tools cannot promise to detect it in general; they instead use restricted grammar classes (like LL or LR) for which freedom from conflicts can be checked mechanically.
The grammar E -> E + E | E * E | id is ambiguous: id + id * id has two parse trees (one grouping the addition first, one grouping the multiplication first). For this one grammar we can SEE the ambiguity, but no algorithm can decide ambiguity for every grammar handed to it.
Spotting ambiguity in one grammar is easy; deciding it for all grammars is impossible.
Ambiguity is a property of the GRAMMAR, not the language — and some languages are inherently ambiguous (every grammar for them is ambiguous). The undecidable question is whether ANY string has two parse trees, not whether one specific string does.