Answer:
See explaination
Explanation:
The post correspondence problem is: Given a_1, \ldots, a_n and b_1, \ldots, b_n , is there a sequence of indices 11. ..., im such that a_{i_1}\ldots a_{i_m} = b_{i_1}\ldots b_{i_m} .
To reduce from the PCP to the ambiguous CFG problem, do the following. Add some more symbols c_1, \ldots, c_n and define the following languages:
L_{A} = \{a_{i_1}\ldots a_{i_k}c_{i_k}\ldots c_{i_1} \mid k \geq 1\}
L_{B} = \{b_{i_1}\ldots b_{i_k}c_{i_k}\ldots c_{i_1} \mid k \geq 1\}
L_{AB} = L_A \cup L_B .
Define the following grammar for the language L_{AB} :
S \to S_{A} \mid S_{B}
S_A \to a_iS_Ac_i \mid a_ic_i, 1 \leq i \leq n
S_B \to b_iS_Bc_i \mid b_ic_i, 1 \leq i \leq n
It is easy to see that the given grammar generates the langauge L_{AB} . The reduction outputs the grammar thus constructed.
To see why this is a valid reduction, let there be a solution to the post correspondence problem, i.e. 11. ..., im such that a_{i_1}\ldots a_{i_m} = b_{i_1}\ldots b_{i_m} . Then the string a_{i_1}\ldots a_{i_m}c_{i_m}\ldots c_{i_1} = b_{i_1}\ldots b_{i_m}c_{i_m}\ldots c_{i_1} has two difference derivations in the given grammar, one using S_A and the other using S_B .
Conversely, let a string generated by the given grammar have two different derivations. Note that S_A and S_B can only generate one derivation tree for any string, hence the only way for two different derivations to happen is for one of them to go to S_A and the other to S_B .
Let the string for which ambiguity appears be of the form a_{i_1}\ldots a_{i_m}c_{i_m}\ldots c_{i_1} . Then the other derivation must produce a string of the form b_{i_1}\ldots b_{i_m}c_{i_m}\ldots c_{i_1} , this is because both derivations must produce the same string for ambiguity to occur, hence the part which uses c_i must be the same. Note that this further implies that a_{i_1}\ldots a_{i_m} = b_{i_1}\ldots b_{i_m} , which is equivalent to saying that the post correspondence problem has a solution.
Hence the reduction works as expected. This proves that the ambiguous CFG problem is undecidable, otherwise post correspondence problem would be decidable, which is a contradiction.
