CYK-алгоритм: синтаксический анализ как задача динамического программирования

Доклад посвящён алгоритму CYK (Кока — Янгера — Касами) — классическому методу синтаксического анализа строк на принадлежность к контекстно-свободным грамматикам, представленным в нормальной форме Хомского. В работе рассматривается идея алгоритма как задачи динамического программирования: построение таблицы разбора, ячейки которой содержат нетерминалы, выводимые из соответствующих подстрок. Приводится пошаговый разбор конкретного предложения, демонстрирующий заполнение таблицы и восстановление вывода. Отдельное внимание уделяется вычислительной сложности алгоритма — O(n³) по времени и O(n²) по памяти, а также границам его применимости.