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.
10
-
$\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 FilmusCommented May 27, 2020 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$– BOB123Commented May 27, 2020 at 8:52
-
$\begingroup$ Do you have an example in which your current approach is double-counting parse trees? $\endgroup$– Yuval FilmusCommented May 27, 2020 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$– BOB123Commented May 27, 2020 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 FilmusCommented May 27, 2020 at 9:03
|
Show 5 more comments