Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики

Пусть дана контекстно-свободная грамматика грамматика [math]\Gamma[/math] и слово [math]w \in \Sigma^{*}[/math]. Требуется выяснить, выводится ли это слово в данной грамматике.

Базовая версия данного алгоритма работает только для грамматик в нормальной форме Хомского. Модифицируем алгоритм для работы на произвольных контекстно-свободных грамматиках.

Алгоритм для произвольной грамматики

Будем решать задачу динамическим программированием. Введём динамику [math]a\left[A,i,j\right] = \left[A \Rightarrow^{*} w[i..j-1]\right][/math], аналогично базовой версии алгоритма.

Также введём вспомогательный четырехмерный массив [math]h\left[A \rightarrow \alpha, i, j, k\right] = true[/math] тогда и только тогда, когда из префикса длины [math]k[/math] правой части данного правила можно вывести [math]w\left[i..j-1\right][/math].

• База динамики:

[math]a\left[A, i, i+1\right] = true[/math], если в грамматике [math]\Gamma[/math] присутствует правило [math]A \rightarrow w[i][/math], иначе [math]a\left[A, i, i+1\right] = false[/math];

[math]a\left[A, i, i\right] = true[/math], если в грамматике [math]\Gamma[/math] присутствует правило [math]A \rightarrow \varepsilon[/math], иначе [math]a\left[A, i, i\right] = false[/math];

[math]\forall A \rightarrow \alpha \:\: h\left[A \rightarrow \alpha, i, i, 0\right] = true[/math] — [math]\varepsilon[/math]-вывод для [math]\varepsilon[/math]-префиксов правил.

• Переход: Пусть для всех подстрок [math]w[i..j-1][/math] динамики уже вычислены. Сначала вычислим вспомогательную динамику: [math]\forall k: h\left[A \rightarrow \alpha, i, j, k\right] = \bigvee\limits_{r=i..j}\left(h\left[A \rightarrow \alpha, i, r, k-1\right] \wedge a\left[\alpha[k],r+1,j\right]\right)[/math]. Это вычисление может обратится к [math]a\left[A,i,j\right][/math], но на результат это не повлияет, так так в данный момент [math]a\left[A,i,j\right]=false[/math].

Главная динамика выражается так: [math]a\left[A,i,j\right]=\bigvee\limits_{A \rightarrow \alpha}h\left[A \rightarrow \alpha, i, j, \left|\alpha\right|\right][/math].

• Завершение: После окончания работы ответ содержится в ячейке [math]a\left[S, 1, n\right][/math], где [math]n = |w|[/math].

Оценка сложности

Обозначим [math]M = \max\limits_{A \rightarrow \alpha}\left|\alpha\right|[/math] — максимальную длину правой части правила.

Расчёт вспомогательной динамики занимает [math]O \left( n^3 \cdot |\Gamma| \cdot M \right)[/math] времени, основной динамики — [math]O \left( n^2 \cdot |\Gamma| \right)[/math]. Итоговая временная сложность алгоритма равна [math]O \left( n^3 \cdot |\Gamma| \cdot M \right)[/math]. Алгоритму требуется [math]O(n^2 \cdot |\Gamma| \cdot M)[/math] памяти.