Изменения

Будем решать задачу динамическим программированием. Введём динамику <tex>a\left[A,i,j\right] = \left[A \Rightarrow^{*} w[i..j]\right]</tex>, аналогично [[Алгоритм_Кока-Янгера-Касами_разбора_грамматики_в_НФХ|базовой версии ]] алгоритма.

* '''База динамики''': <tex>a\left[A, i, i\right] = true</tex>, если в грамматике <tex>\Gamma</tex> присутствует правило <tex>A \rightarrow w[i]</tex>, иначе <tex>a\left[A, i, i\right] = false</tex>. <tex>a\left[A, i, i\right] = \left[ A \rightarrow w[i] \in P \right]</tex> — вывод терминалов, <tex>a\left[A, i, i-1\right] = \left[ A \rightarrow \varepsilon \right]</tex> — <tex>\varepsilon</tex>-вывод; <tex>\forall A \rightarrow \alpha \:\: h\left[A \rightarrow \alpha, i, i-1, 0\right] = true</tex> — <tex>\varepsilon</tex>-вывод для <tex>\varepsilon</tex>-префиксов правил.

<tex>a\left[A, i, i\right] = true</tex>, если в грамматике <tex>\Gamma</tex> присутствует правило <tex>A \rightarrow w[i]</tex>, иначе <tex>a\left[A, i, i\right] = false</tex>;  <tex>a\left[A, i, i-1\right] = true</tex>, если в грамматике <tex>\Gamma</tex> присутствует правило <tex>A \rightarrow \varepsilon</tex>, иначе <tex>a\left[A, i, i-1\right] = false</tex>;  <tex>\forall A \rightarrow \alpha \:\: h\left[A \rightarrow \alpha, i, i-1, 0\right] = true</tex> — <tex>\varepsilon</tex>-вывод для <tex>\varepsilon</tex>-префиксов правил. * '''Переход''': Пусть для всех подстрок <tex>w[i..j]</tex> динамики уже вычислены. Сначала вычислим вспомогательную динамику: <tex>\forall k: h\left[A \rightarrow \alpha, i, j, k\right] = \bigvee\limits_{r=i-1..j}\left(h\left[A \rightarrow \alpha, i, r, k-1\right] \wedge a\left[\alpha[k],r+1,j\right]\right)</tex>. Это вычисление может обратится к <tex>a\left[A,i,j\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>.