Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ

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

Алгоритм для НФХ-грамматики

Пусть [math]\Gamma[/math] приведена к НФХ.

Представим [math]a_{A, i, j} = true[/math], если можно из [math]A[/math] вывести подстроку [math]w[i..j][/math]. Иначе [math]a_{A, i, j} = false[/math].

[math]a_{A, i, j} = \lbrack A \Rightarrow^{*} w[i..j] \rbrack[/math].

Базой динамики являются ячейки [math]a_{A, i, i}[/math], которые заполняются истиной, если правило [math]A \rightarrow w[i][/math] принадлежит грамматике: [math]a_{A, i, j} = \lbrack A \rightarrow w[i] \in P \rbrack[/math].

Переход динамики имеет вид: [math]a_{A, i, j} = \bigvee\limits_{k=i}^{j-1} \bigvee\limits_{A \rightarrow BC} \left( a_{B, i, k} \wedge a_{C, k+1, j} \right)[/math].

Пусть на текущем шаге [math]j-i=k[/math]. Тогда мы смотрим, можно ли вывести подстроку [math]w[i..j][/math] из ячеек матрицы, для которых [math]j-i\lt k[/math] и [math]A \rightarrow BC[/math].

По окончанию динамики ответ будет содержаться в ячейке [math]a_{S, 1, n}[/math], где [math]n = |w|[/math].

Сложность алгоритма

Необходимо вычислить [math]n^2[/math] булевских величин. На каждую требуется затратить [math]n \cdot |P_A|[/math] операций, где [math]|P_A|[/math] – количество правил,. Суммируя по всем правилам получаем конечную сложность [math]O \left( n^3 \cdot |\Gamma| \right)[/math].

Алгоритму требуется [math]n^2 \cdot |N|[/math] памяти, где [math]|N|[/math] – количество нетерминалов грамматики.

Минус алгоритма заключается в том, что изначально грамматику необходимо привести к НФХ.