Изменения
Нет описания правки
Также введём вспомогательный четырехмерный массив <tex>h\left[A \rightarrow \alpha, i, j, k\right] = true</tex> тогда и только тогда, когда из префикса длины <tex>k</tex> правой части данного правила можно вывести <tex>w\left[i..j-1\right]</tex>.
Рассмотрим все пары <tex>\lbrace \langle j, i \rangle | j-i=m \rbrace</tex>, где <tex>m</tex> {{---}} константа и <tex>m < n</tex>.
* '''База динамики''':
<tex>a\left[A, i, i+1\right] = true</tex>, если в грамматике <tex>\Gamma</tex> присутствует правило <tex>A \rightarrow w[i]</tex>, иначе <tex>a\left[A, i, i+1\right] = false</tex>;
<tex>\forall A \rightarrow \alpha \:\: h\left[A \rightarrow \alpha, i, i, 0\right] = true</tex>.
* '''Переход''': Пусть значения для всех нетерминалов и пар <tex>\lbrace \langle j', i' \rangle | j' - i' < m \rbrace</tex> уже вычислены. Давайте вычислим вспомогательную динамику, поэтому вспомогательная динамика: <tex>\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)</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>.
