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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,644 questions

56,539 answers

195,661 comments

101,444 users