¿Es correcto el resultado de este analizador CYK?

Question

Estoy tratando de aprender el Algoritmo de análisis CYK.

Para este conjunto de reglas gramaticales, ¿son correctas las tablas resultantes para las dos oraciones dadas?

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

Puedes intentar minimizar tu gramática primero, porque hay algunas reglas innecesarias y además es por eso que es not in CNF.

Viéndolo de manera más concisa, resulta que tienes None en el primer ejemplo, segunda fila, segunda columna.Allí es realmente posible tener una S, pero dado que la lógica en CYK no puede realizar más optimizaciones como NP->NN.Desde allí S -> NP VP para los mencionados None la celda se pierde.Debido a la incapacidad de CYK para realizarlos, la gramática debe estar en CNF.Entonces, básicamente es como si estuvieras intentando aplicar un compilador de C en un programa de C++ (sin bibliotecas de C++).y tienes afortunado incluso para obtener el resultado correcto en la parte superior.

Dicho esto, no voy a permitirme el segundo ejemplo suyo.

Sólo para aclarar, hay una gramática en CNF si tiene reglas solo de estas dos formas:

S->AB
Un -> un

tan claramente algo como NP -> NN no está en CNF.