Изменения

[[Алгоритм_Кока-Янгера-Касами_разбора_грамматики_в_НФХ|Базовая версия]] данного алгоритма работает только для грамматик в [[нормальная форма Хомского|нормальной форме Хомского]]. Модифицируем алгоритм для работы на произвольных контекстно-свободных грамматиках. В отличии от базовой версии, нам не важны [[Удаление_цепных_правил_из_грамматики|цепные правила]] и [[Удаление_eps-правил_из_грамматики|<tex>\varepsilon</tex>-правила]].

* '''Переход''': Пусть значения для всех нетерминалов, пар <tex>\lbrace \langle j', i' \rangle | j' - i' < m \rbrace</tex> и <tex>\lbrace k' | k' < k \rbrace</tex> уже вычислены, поэтому вспомогательная динамика: <tex>\forall k: h\left[A \rightarrow \alpha, i, j+1, k\right] = \bigvee\limits_{r=i..j+1}\left(h\left[A \rightarrow \alpha, i, r, k-1\right] \wedge a\left[\alpha[k],r+1,j+1\right]\right)</tex>. То есть, подстроку <tex>w[i \dots j]</tex> можно вывести из префикса длины <tex>k</tex> правой части данного правила, если из префикса длины <tex>k-1</tex> правой части данного правила можно вывести <tex>w\left[i..j-1\right]</tex>, а подстрока <tex>w[r \dots j]</tex> выводится из правой части данного правила. Это вычисление может обратится к <tex>a\left[A,i,j+1\right]</tex>, но на результат это не повлияет, так так в данный момент <tex>a\left[A,i,j\right]=false</tex>.

Главная динамика выражается так: <tex>a\left[A,i,j\right]=\bigvee\limits_{A \rightarrow \alpha}h\left[A \rightarrow \alpha, i, j, \left|\alpha\right|\right]</tex>.То есть, подстроку <tex>w[i \dots j-1]</tex> можно вывести из нетерминала <tex>A</tex>, если из длины правой части данного правила можно вывести <tex>w\left[i..j-1\right]</tex>,