Theorem: It is undecidable whether or not the languages generated by two given context-free grammars have an empty intersection.

Proof: By a reduction of post correspondence problem (which is known to be undecidable) to the empty intersection problem.
Given a set d₁,...,d_n of dominos where, for i=1,...,n, the top string of d_i is w_i and the bottom string of d_i = x_i. Consider the context-free grammars

W -> w₁W d₁ | w₂W d₂ | ... | w_nW d_n | w₁ d₁ | w₂ d₂ | ... | w_n d_n |
and
X -> x₁X d₁ | x₂X d₂ | ... | x_nX d_n | x₁ d₁ | x₂ d₂ | ... | x_n d_n |

Now notice that the given instance of PCS has a match exactly when the intersection of the languages generated by the resulting grammars above is nonempty.

Theorem: It is undecidable whether or not a given context-free grammar is ambiguous.

Proof: Given an instance of PCP, create the grammar G with productions S -> W | X and the productions for X and W above. Now the given instance has a match exactly when G is ambiguous.

Rob van Glabbeek

rvg@cs.stanford.edu