) Consider the ambiguous CFG problem: given a context free grammar, does there exist a string that can be generated by two different parse trees. Show that this problem is undecidable by reducing the post correspondence problem to it. The post correspondence problem is the following: given two sequences of strings a1, ..., an and b1, ..., bn, is there a sequence of indices i1, ..., im (with possibly repeats, and whose total length may be much bigger than n) such that ai1 ai2 ...aim = bi1 bi2 ...bim?

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.