Изменения

Будем решать задачу [[Динамическое_программирование|динамическим программированием]]. Заведем трехмерный массив d, состоящий из логических значений, и <tex>d[A][i][j] = true</tex> тогда и только тогда, когда из нетерминала <tex>A</tex> правилами грамматики можно вывести подстроку <tex>w[i..\dots j]</tex>.

\После окончания работы значение <tex>d[S][1][n]</tex> содержит ответ на вопрос, выводима ли данная строка в данной грамматике.

Пусть === Количество способ вывести слово ===Если массив будет хранить целые числа, а формулу заменить на <tex>P_d[A][i][j] = \sum\limits_{A \rightarrow BC}\sum\limits_{k = i}^{j-1} d[B][i][k] \cdot d[C][k + 1][j]</tex>, то <tex>d[A][i][j]</tex> - количество способов получить подстроку <tex>w[i \dots j]</tex> из нетерминала <tex>A</tex>. === Минимальная стоимость вывода слова ===Пусть <tex>P(A \rightarrow BC)</tex> - ''стоимость'' вывода по правилу <tex>A \rightarrow BC</tex>. Тогда, если использовать формулу <tex>d[A,][i,][j] = \min\limits_{A \rightarrow BC} \min\limits_{k = i}^{j-1} ( d[B,][i,][k] + d[C,][k+1,][j] + P_{P(A \rightarrow BC} ) )</tex>, то <tex>d[A,][i,][j]</tex> - минимальная стоимость вывода подстроки <tex>a_i...a_jw[i \dots j]</tex> из нетерминала <tex>A</tex>.

d[A][i][i] = ''true''

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