# modifing CYK to compute the number of different parsing trees of a given sentence

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.

• 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. – Yuval Filmus May 27 at 8:51
• @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 – omrib40 May 27 at 8:52
• Do you have an example in which your current approach is double-counting parse trees? – Yuval Filmus May 27 at 8:54
• 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? – omrib40 May 27 at 9:02
• Can you give a concrete example? That is, a CFG and a bad run of your modified CYK algorithm. Add it to your post. – Yuval Filmus May 27 at 9:03