Let $AMBIG_{CFG} = \{\langle G \rangle \mid \text{G is an ambiguous CFG}\}$. Show that $AMBIG_{CFG}$ is undecidable.
(Hint: Use a reduction from $PCP$. Given an instance
$P = \begin{Bmatrix} \bigg[\dfrac{t_{1}}{b_{1}}\bigg],&\bigg[\dfrac{t_{2}}{b_{2}}\bigg],\dots &,\bigg[\dfrac{t_{k}}{b_{k}}\bigg] \end{Bmatrix}$
of the Post Correspondence Problem, construct a $CFG\:\: G$ with the rules
- $S\rightarrow T \mid B$
- $T \rightarrow t_{1}Ta_{1} \mid \dots \mid t_{k}Ta_{k} \mid t_{1}a_{1} \mid \dots \mid t_{k}Ta_{k}$
- $B \rightarrow b_{1}Ba_{1} \mid \dots \mid b_{k}Ba_{k} \mid b_{1}a_{1} \mid \dots \mid b_{k}Ta_{k},$
where $a_{1},\dots,a_{k}$ are new terminal symbols. Prove that this reduction works.)