Question

Let $AMBI{G}_{CFG}=\left\{<G>|GisanambiguousCFG\right\}$. Show that AMBIG_CFG is undecidable. (Hint: Use a reduction from PCP. Given an instance

$P=\left\{\left[\frac{t_1}{b_1}\right],\left[\frac{t_2}{b_2}\right],\dots ,\left[\frac{t_k}{b_k}\right]\right\}$

of the Post Correspondence Problem, construct a CFG Gwith the rules

$S\to T|B$

$T\to t_1{T}_{a_1}|.....|t_k{T}_{a_k}\left|t_1{a}_1\right|....|t_k{a}_k$

$B\to b_{1}B|...|b_1{B}_{a_k}|...|b_k{a}_k$

where a₁,...,a_k are new terminal symbols. Prove that this reduction works.)

Short answer

It is proved that AMBIG_CFG is undecidable.

Step-by-step solution

Introduction to PCP and Undecidable

Post Correspondence Problem (PCP)

Post Corresponding Problem is undecidable problem where we have more than one tile which contains multiple strings. The goal of this problem is to arrange the order of strings such that the numerator and denominator are identical.

In Post Correspondence Problem (PCP), we try to find the pattern in which upper and lower strings are identical.

Undecidable

A problem is undecidable if no Turing Machine exist which will halt in finite amount of time

Proving AMBIGCFG undecidable

We need to notice that:

• 1. If it is possible that P has a match like $t_{i_1}{t}_{i_2}....t_{i_l}=b_{i_1}{b}_{i_2}...b_{i_l}$, then we can observe that the string $t_{i_1}{t}_{i_2}...t_{i_l}{a}_{i_l}...a_{i_2}{a}_{i_1}$ have two derivations where, one derivative is from T and other one is from B .
• 2. If Context Free Grammar G is ambiguous, in such case some strings ‘s’ will have more then two derivations.
• Now as s is produced by G , so we can express it as: $w{a}_{j_1}{a}_{j_2}.....a_{j_m}$ for some value of w which didn’t contain symbol from set a_i's .

  By looking at the grammar G , we can see that the derivative of T and B can generate at most one string of form ‘s’.

  So, the multiple derivation of ‘s’ must be express for T and B as follows:

  $S\Rightarrow T\dot{\Rightarrow }s=t_{j_m}{t}_{j_{m-1}}\dots t_{j_1}{a}_{j_1}{a}_{j_2}\dots a_{j_m}$

  $S\Rightarrow B\dot{\Rightarrow }s=b_{j_m}{b}_{j_{m-1}}\dots b_{j_1}{a}_{j_1}{a}_{j_2}\dots a_{j_m}$S

• so clearly from above two equations we observe that,
  $t_{j_m}{t}_{j_{m-1}}\dots t_{j_1}=b_{j_m}{b}_{j_{m-1}}\dots b_{j_1}$
  
  And we can get a match of P from above equation.
  So, on combining the observation (1) and (2) which we mentions at starting of our answer, P have a match if and only if G is ambiguous grammar.
  We are able to reduce from Post Correspondence Problem to AMBIG_CFG .
  Thus, AMBIG_CFG is undecidable.