How to show that this language is Turing recognizable

Question

So this question has two questions and i have to use the answer from 1 to answer question 2. Assuming that my answer for 1 is good. I need help with 2. ( Correct me if wrong please.)

Question 1 :

Show that this language is decidable

The language is $L=$ { $< G,w > $ : $G$ is a grammar in normal form of Chomsky and $w$ is a word on the terminal alphabet that can be derivated in $G$ by at least 2 differents derivations trees. }

In other words, find an algorithm that when given a grammar that is in normal form of Chomsky and a word $w$, it concludes after a finite number of steps if yes or no $w$ can be derivated by two derivations trees.

Here's my attempt (correct me if this is wrong) :

Entry : < G, w >;

1. Try every derivations in $G$ of length $2|w| -1$.
2. If two derivations generate w stop and accept < G,w >. Else stop and reject < G,w >.

Question 2

Show that this language is Turing recognizable $K =$ { < G > : G is a grammar in normal form of Chomsky and G is ambiguous ( can have two derivation tree for same word).} In other words, give an algorithm that when given an grammar in normal form of Chomsky, it returns "true" if $G$ is ambiguous and return "false" or doesn't stop when $G$ is not ambiguous. ( Give an answer absed on the algorithm used in question 1)

My reflexion on question 2 :

For this part i am kinda lost, i know that we will use algorithm of question 1 to be able to return true but for the infinite loop part i am not sure on how to say this.

I am also not sure if i can use a word "w" since our entry is a grammar G.

Entry : < G >

1. Apply algorithm from question 1 if it returns true, return true. ( Because question 1 basically confirm that the CNF is ambiguous).

2. note sure how to handle the rest for it to loop.

Thanks a lot for your help.

Answer 1

In order to recognize a ambiguous CFG in Chomsky normal form, you only need to find a certificate string to show that it can be derived by at least two heterogeneous trees. Now that you have figured out how to verify whether a given string $w$ can be derived ambiguously, a method of simply enumerating every string over the alphabet in the string order works.

Aside: This language is notoriously known to be undecidable. PCP can be reduced to it by a computable function (It is easy to modify the original function in a way such that it always produces unambiguous Chomsky normal form for every possible list of symbols on the top of the dominos and on the bottom alike). Hence, it is $\Sigma_1$-complete.