Given a CFG in Chomsky Normal Form and a sentence s. I want to count the number of different parsing trees that parses s. assuming I know how to change the CYK algorithm so it would count the number of parsing trees, how can I determine if one tree X is different then tree Y? obviously it can be done in a naive way that I would save all my current parse trees and for every new tree I would check if it already exists but it's time-consuming and space-consuming as It requires to save all the previous parsing trees in a data structure... I would like to avoid that.

  • $\begingroup$ Use the exact same recurrences as in CYK, but keep track of the number of parse trees instead of just whether there is a part tree. $\endgroup$ – Yuval Filmus May 27 at 8:51
  • $\begingroup$ @YuvalFilmus i believe this is not answering my question, I did modify the CYK to count the number of parsing trees, but not count the number of different parsing trees as required...my issue is determine efficiently if tree X equals tree Y $\endgroup$ – omrib40 May 27 at 8:52
  • $\begingroup$ Do you have an example in which your current approach is double-counting parse trees? $\endgroup$ – Yuval Filmus May 27 at 8:54
  • $\begingroup$ isn't it a problem if i have 2 rules of the form X->AB Y->AB? i might not fully understand what is the meaning of 2 different parsing trees, for my understanding 2 parsing trees are equal if we run in-order traversal and for every node x in tree X it equals to node y in tree Y in the same order...is it right? $\endgroup$ – omrib40 May 27 at 9:02
  • $\begingroup$ Can you give a concrete example? That is, a CFG and a bad run of your modified CYK algorithm. Add it to your post. $\endgroup$ – Yuval Filmus May 27 at 9:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.