undecidable grammar problems
Context-free grammars are friendly enough that some questions about them ARE decidable: is the language empty, is a given string in the language, is the language finite. But push a little harder and you hit a wall of impossibility. Several natural, practically-motivated questions about grammars have no algorithm at all. The surprising part is which ones, and the tool that proves it is almost always the Post correspondence problem.
Here is the gallery of undecidable grammar questions. Ambiguity: given a context-free grammar, does some string have two different parse trees? Equivalence: do two given grammars generate exactly the same language? Universality: does a grammar generate every string over its alphabet (is its language all of Sigma-star)? Intersection-emptiness: do two given context-free languages share any common string? And inclusion: is one context-free language contained in another? Each of these is undecidable. The standard proof reduces PCP to the grammar question: from a box of dominoes you build grammars whose derivations encode possible top-sequences and bottom-sequences, rigged so that a string with two parse trees, or a shared string, or a missing string, corresponds precisely to a domino matching. Since deciding the matching is impossible, deciding the grammar property is impossible.
Two honest contrasts keep this straight. First, the analogous questions for finite automata and regular languages ARE decidable: equivalence of DFAs, emptiness, even universality, all have algorithms, because regular languages are closed under complement and intersection and DFAs can be minimized. Context-free languages are NOT closed under intersection or complement, and that closure failure is precisely what opens the door to undecidability. Second, membership and emptiness for a single context-free grammar remain decidable; it is the comparative and 'for-all-strings' questions, ambiguity and equivalence and universality, that cross the line. This is why real compiler tools cannot, in general, just check 'is my grammar unambiguous' and instead rely on restricted, decidable grammar classes like LL and LR.
From a PCP box, build a grammar G that can derive a string in two ways: one parse tree spelling a top-sequence and another spelling the matching bottom-sequence. G is ambiguous if and only if the box has a matching, i.e. a PCP solution. Since PCP is undecidable, deciding whether G is ambiguous is undecidable too.
PCP is reduced to grammar ambiguity: a matching becomes a string with two parse trees.
The SAME questions are decidable for regular languages / DFAs (equivalence, universality, intersection-emptiness all have algorithms). It is the failure of CFLs to be closed under intersection and complement that makes the grammar versions undecidable.