2 views

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.)

retagged | 2 views