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 $

  1. Try every derivations in $G$ of length $2|w| -1$.
  2. 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 "true" if $G$ is ambiguous and return "false" 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 "$w$" since our entry is a grammar $G$.

Entry : $\langle G \rangle$

  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.

  • $\begingroup$ Welcome to CS.SE. Please ask only one question per post. If you have two questions, it is better to ask them in two separate posts. Beware that we discourage "please check whether my answer is correct" questions (as they're unlikely to be useful to others in the future) or "please solve my exercise for me" questions (as they're unlikely to help people learn concepts). Thank you. $\endgroup$
    – D.W.
    Commented Nov 28, 2020 at 22:13
  • $\begingroup$ @D.W. Thanks, my question is about the question 2, but it uses the quesiton 1 that's why i needed to post them together :) $\endgroup$
    – codetime
    Commented Nov 28, 2020 at 22:22

1 Answer 1


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.

  • $\begingroup$ thanks for reply, so if i understnad, my step 1 for question 2 is good. But i am still confused on how to write what to do on step 2 ( the rejecting and infinite loop part). What would i say to explain this part ? Thanks a lot. $\endgroup$
    – codetime
    Commented Dec 1, 2020 at 3:15
  • $\begingroup$ @codetime, please come here for a chat. $\endgroup$
    – John L.
    Commented Dec 1, 2020 at 11:06
  • $\begingroup$ ok i replied in the google drive ! $\endgroup$
    – codetime
    Commented Dec 1, 2020 at 16:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.