**Proof:** By a reduction of post correspondence problem (which is
known to be undecidable) to the empty intersection problem.

Given a set d_{1},...,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_{1}W d_{1} |
w_{2}W d_{2} | ... | w_{n}W d_{n} |
w_{1} d_{1} |
w_{2} d_{2} | ... | w_{n} d_{n} |

and

X -> x_{1}X d_{1} |
x_{2}X d_{2} | ... | x_{n}X d_{n} |
x_{1} d_{1} |
x_{2} d_{2} | ... | x_{n} d_{n} |

**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 |