How to show ambiguous context-free grammars in Chomsky normal form is Turing recognizable? 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 the following language is decidable

$L=\{\langle G,w \rangle $ : $G$ is a grammar in normal form of Chomsky and $w$ is a word on the terminal alphabet that can be derived 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 derived by two derivations trees.
Here's my attempt (correct me if this is wrong) :
Entry : $\langle G,w \rangle $

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

Question 2 :
Show that this language is Turing recognizable $K = \{\langle G \rangle : 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 &quot;true&quot; if $G$ is ambiguous and return &quot;false&quot; or doesn't stop when $G$ is not ambiguous. ( Give an answer based 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 &quot;$w$&quot; since our entry is a grammar $G$.
Entry : $\langle G \rangle$

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

note sure how to handle the rest for it to loop.
Your answer to question 1 is nice and correct.

On question 2, of course, you can use a single word $w$ to test the grammar $G$. However, it is not enough to use just one word, since the grammar could be ambiguous on another word.
Well, we can use all words to test the grammar.
Here is the high-level description of a Turing machine $R$ that recognizes $K$.

Loop through all words:

for each word $w$, try every derivation in $G$ of length $2|w|−1$.
If two derivations generate $w$ stop the machine and accept $G$.


There are many ways to loop through all words. For example, we can fix an arbitrary order of all terminals and iterate by short-lexicographic order.
Note that when $G$ is not ambiguous, $R$ will run forever. That means $R$ is not a decider for $K$. In fact, no Turing machine can decide $K$ since $K$ is undecidable.