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

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

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

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

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

Введём вспомогательную динамику: [math]h_{A \rightarrow \alpha, i, j, k} = \left[\alpha\left[1..k\right] \Rightarrow^* w\left[i..j\right]\right] \quad \left(\forall A \rightarrow \alpha \in \Gamma\right)[/math], где [math]k \le M[/math] — можно ли из префикса длины [math]k[/math] правой части данного правила вывести [math]w\left[i..j\right][/math]. Также введём динамику [math]a_{A,i,j} = \left[A \Rightarrow^{*} w[i..j]\right][/math], аналогично базовой версии алгоритма.

• База динамики: [math]a_{A, i, i} = \left[ A \rightarrow w[i] \in P \right][/math] — вывод терминалов, [math]\forall i \:\: a_{A, i, i-1} = \left[ A \rightarrow \varepsilon \right][/math] — [math]\varepsilon[/math]-вывод, [math]\forall i,A \rightarrow \alpha \:\: h_{A \rightarrow \alpha, i, i-1, 0} = true[/math] — [math]\varepsilon[/math]-вывод для [math]\varepsilon[/math]-префиксов.

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

• Завершение: После окончания работы ответ содержится в ячейке [math]a_{S, 1, n}[/math], где [math]n = |w|[/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] памяти.