Este resultado do analisador CYK está correto?

Question

Estou tentando aprender o Algoritmo de análise CYK.

Para este conjunto de regras gramaticais, as tabelas resultantes estão corretas para as duas sentenças fornecidas?

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

Você pode tentar minimizar sua gramática primeiro, porque existem algumas regras desnecessárias e, além disso, é por isso que é not in CNF.

Olhando de forma mais concisa, você tem None no primeiro exemplo, segunda linha, segunda coluna.Lá é realmente possível ter um S, mas como a lógica em CYK não pode fazer otimizações adicionais, como NP->NN.De lá S -> NP VP para o mencionado None celular desaparece.Devido à incapacidade do CYK de realizá-los, a gramática deve estar em CNF.Então, basicamente é como se você estivesse tentando aplicar um compilador C em um programa C++ (sem bibliotecas C++).E você tem sortudo para obter o resultado certo no topo.

Dito isso, não vou me entregar ao segundo exemplo seu.

Só para esclarecer, uma gramática está em CNF se tiver regras apenas destas duas formas:

S ->AB
Um -> um

tão claramente algo como NP -> NN não está na CNF.