418
правок
Изменения
Псевдокод!
{{Задача
|definition =
Пусть дана [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]] грамматика <tex>\Gamma</tex> в [[нормальная форма Хомского|нормальной форме Хомского]] и слово <tex>w \in \Sigma^{*}</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>w[i \dots j]</tex> из нетерминала <tex>A</tex>.
