Изменения

Пусть дана строка <tex>a_1 a_2 ... a_n</tex>. Заведем трехмерный массив d, состоящий из логических значений, и <tex>d[A][,i,j] = true</tex> тогда и только тогда, когда из нетерминала <tex>A</tex> правилами грамматики можно вывести подстроку <tex>a_i a_{i+1} ... a_j</tex>. Тогда:* <tex>d[A][,i,i] = true</tex>, если в грамматике присутствует правило <tex>A \Rightarrow a_i</tex>, иначе <tex>false</tex>* Остальные элементы массива заполняются динамически: <tex>d[A][,i,j] = \bigvee\limits_{A \Rightarrow BC}\bigvee\limits_{k = i}^{j-1} d[B][,i,k] \wedge d[C][,k+1,j]</tex>. То есть, подстроку <tex>a_i...a_j</tex> можно вывести из нетерминала <tex>A</tex>, если существует продукция <tex>A \Rightarrow BC</tex> и такое <tex>k</tex>, что подстрока <tex>a_i...a_k</tex> выводима из <tex>B</tex>, а подстрока <tex>a_{k+1}...a_j</tex> - из <tex>C</tex>.

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

Заметим, что если массив будет хранить целые числа, а формулу динамики заменить на <tex>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>a_i...a_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_{A \Rightarrow BC} )</tex>, то <tex>d[A][,i,j]</tex> - минимальная стоимость вывода подстроки <tex>a_i...a_j</tex> из нетерминала <tex>A</tex>.