The Gateway to Computer Science Excellence
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.)

in Theory of Computation by Veteran (60.8k points)
retagged by | 6 views

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,833 questions
57,736 answers
107,925 users