Изменения

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

Пусть <tex>\Gamma</tex> приведена к НФХ[[нормальная форма Хомского|нормальной форме Хомского]].

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

<tex>a_{A, i, j} = \lbrack begin{cases}true,&\text{$A \Rightarrow^{*} w[i..j] $;}\rbrack\false,&\text{else.}\end{cases}</tex>.

Базой динамики являются ячейки *'''База'''. Ячейки <tex>a_{A, i, i}</tex>, которые заполняются истиной, если правило <tex>A \rightarrow w[i]</tex> принадлежит грамматикемножеству правил <tex>P</tex> грамматики <tex>\Gamma</tex>:

 *'''Переход динамики имеет вид'''. Пусть на текущем шаге <tex>j-i=m>0</tex>. Если все ячейки, для которых справедливо <tex>j-i<m</tex>, уже вычислены, то алгоритм смотрит, можно ли вывести подстроку <tex>w[i..j]</tex> из этих ячеек:

Пусть на текущем шаге <tex>j-i=k</tex>. Тогда мы смотрим, можно ли вывести подстроку <tex>w[i..j]</tex> из ячеек матрицы, для которых <tex>j-i<k</tex> и <tex>A \rightarrow BC</tex>*'''Завершение'''. По окончанию динамики После окончания работы ответ будет содержаться содержится в ячейке <tex>a_{S, 1, n}</tex>, где <tex>n = |w|</tex>. 

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