¿Es correcto el resultado de este analizador CYK?
-
13-12-2019 - |
Pregunta
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']
Solución
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.