Правильный ли результат парсера CYK?

Question

Я пытаюсь изучить Алгоритм анализа CYK.

Верны ли полученные таблицы для этого набора грамматических правил для двух данных предложений?

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

Вы можете сначала попытаться свести к минимуму свою грамматику, потому что есть некоторые ненужные правила, и, более того, именно поэтому это так. not in CNF.

Глядя на это более кратко, у вас есть None в первом примере вторая строка, второй столбец.Там действительно можно иметь S, но поскольку логика в CYK не может выполнять дальнейшую оптимизацию, такую ​​как NP->NN.Оттуда S -> NP VP для упомянутого None клетка пропадает.Из-за неспособности CYK выполнить это, грамматика должна быть в CNF.По сути, это примерно похоже на то, как если бы вы пытались применить C-компилятор к программе на C++ (без библиотек C++).И ты получил удачливый чтобы даже получить правильный результат наверху.

Учитывая вышесказанное, я не собираюсь останавливаться на втором вашем примере.

Чтобы внести ясность, грамматика находится в CNF если там есть правила только из этих двух форм:

С -> АБ
А -> а

так ясно что-то вроде NP -> NN нет в CNF.