Est-ce CYK analyseur résultat correct?

Question

Je suis en train d'apprendre le CYK algorithme d'analyse d'.

Pour cet ensemble de règles de grammaire, sont les tables de correct pour les deux phrases?

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

Vous pouvez essayer de réduire votre grammaire d'abord, parce qu'il y a certaines règles inutiles et en outre c'est pourquoi il est not in CNF.

En le regardant de façon plus concise, il vous arrive d'avoir None sur le premier exemple, la deuxième ligne, deuxième colonne.Là, il est en fait possible d'avoir un S, mais , depuis la logique de CYK ne peut pas effectuer d'autres optimisations telles que NP->NN.À partir de là S -> NP VP pour le mentionné None la cellule disparaît.En raison de CYK l'incapacité d'effectuer ces, la grammaire doit être en CNF.Donc, fondamentalement, c'est à peu près comme vous essayez d'appliquer un compilateur C sur C++ programm (avec pas de bibliothèques C++).Et vous l'avez obtenu de la chance de même obtenir le bon résultat au top.

Avec cela étant dit, je ne vais pas me livrer dans le deuxième exemple de la vôtre.

Juste pour préciser, une grammaire est en CNF si il y a des règles seulement de ces deux formes:

S -> AB
A -> a

donc clairement, quelque chose comme NP -> NN n'est pas dans CNF.