Действительно ли CKY требует CNF?

Я прочитал ряд мест, где алгоритмы CYK/CKY требуют, чтобы грамматика была в нормальной форме Хомского (CNF), например

Стандартная версия CYK работает только с контекстно-свободными грамматиками дано в нормальной форме Хомского (CNF) ~ Wikipedia

Тем не менее, я также видел ряд примеров алгоритмов CKY, где грамматика не была в CNF. Общий пример, который использует Кристофер Мэннинг,- это "аквариумы для Рыб" (ref: PPT slide #19 ), который содержит унарные правила: 
S -> NP VP [0.9]
S -> VP [0.1]
VP -> V NP [0.4]
Vp -> V [0.6]
...

Я также видел другие примеры, демонстрирующие CKY, которые используют три не-терминала в RHS производства (например,VP -> Verb NP NP Ссылка ). Почему такое несоответствие?

1 4
nlp grammar context-free-grammar

1 ответ:

Время выполнения CYK зависит от длины самого длинного производственного правила, так как алгоритм рассматривает все возможные способы разложения строки на k частей для производства длины k. это означает, что время выполнения на фазу равно O(nk), где k-длина самого длинного производственного правила. Поскольку существует O(n) фаз, время выполнения CYK на грамматике с максимальной производительностью длины k равно O (nk+1).

CYK будет корректно работать с грамматиками, которые не находятся в CNF, но время выполнения не может быть кубическим по длине строки. Требование CNF просто заставляет k = 2 и поэтому гарантирует O(n3) Общее время выполнения.

6