retagged by
384 views
0 votes
0 votes

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 by

Please log in or register to answer this question.

Related questions

0 votes
0 votes
0 answers
1
admin asked Oct 19, 2019
303 views
In the silly Post Correspondence Problem, $SPCP$, the top string in each pair has the same length as the bottom string. Show that the $SPCP$ is decidable.
0 votes
0 votes
0 answers
2
0 votes
0 votes
0 answers
3
0 votes
0 votes
0 answers
4