Is this CYK parser result correct?

Question

I am trying to learn the CYK parsing algorithm.

For this set of grammar rules, are the resulting tables correct for the two given sentences?

S -> NP VP
VP -> VB NP
NP -> DT NN
PP -> IN NP
NP -> NP PP
NP -> NN
VP -> VP PP
IN -> with
NN -> dog
NN -> cat
VB -> ate
NN -> mouse
DT -> the


['S']
[None, None]
[None, None, 'VP']
['NP', None, None, 'NP']
['DT', 'NN', 'VB', 'DT', 'NN']
['the', 'cat', 'ate', 'the', 'dog']


['S']
['NP', None]
['NP', None, 'VP']
['NP', None, None, 'NP']
[None, None, 'VP', None, None]
[None, None, 'VP', None, None, 'PP']
['NP', None, None, 'NP', None, None, 'NP']
['DT', 'NN', 'VB', 'DT', 'NN', 'IN', 'DT', 'NN']
['the', 'cat', 'ate', 'the', 'dog', 'with', 'the', 'cat']

Answer 1

You can try to minimize your grammar first, because there are some unnecessary rules and furthermore that's why it is not in CNF.

Looking at it more concisely, you happen to have None on the first example, second row, second column. There it is actually possible to have a S, but since the logic in CYK cannot do further optimizations such as NP->NN. From there S -> NP VP for the mentioned None cell goes missing. Because of CYK's inability to perform those, the grammar must be in CNF. So, basically it is roughly like you are trying to apply a C-compiler on a C++ programm (with no C++ libraries). And you got lucky to even get the right result at the top.

With that being said, I am not going to indulge in the second example of yours.

Just to clarify, a grammar is in CNF if it has rules only of these two forms:

S -> AB
A -> a

so clearly something like NP -> NN is not in CNF.

Answer 2

Although the given grammar is not in Chomosky normal form, we can easily convert it to CNF like the following one (e.g., get rid of the illegal production NP -> NN and augment the grammar with additional rules):

S -> NP VP
S -> NN VP
VP -> VB NP
VP -> VB NN
NP -> DT NN
PP -> IN NP
PP -> IN NN
NP -> NP PP
NP -> NN PP
VP -> VP PP
IN -> with
NN -> dog
NN -> cat
VB -> ate
NN -> mouse
DT -> the

With the grammar modified to the above one the DP table with CYK algorithm (refer to the implementation here, although it assumes each symbol in the grammar to be a single character in length, but can easily be extended) will be like the following one, for the first sentence:

It will have the following parse tree:

with the 2nd sentence, the following animation shows the DP table generated,

with the following parse tree: