54
правки
Изменения
м
→Алгоритм Кока-Янгера-Касами
Пусть дана строка <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 rightarrow a_i</tex>, иначе <tex>false</tex>* Остальные элементы массива заполняются динамически: <tex>d[A,i,j] = \bigvee\limits_{A \Rightarrow 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 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 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 rightarrow BC}</tex> - ''стоимость'' вывода по правилу <tex>A \Rightarrow rightarrow BC</tex>. Тогда, если использовать формулу <tex>d[A,i,j] = \min\limits_{A \Rightarrow rightarrow BC} \min\limits_{k = i}^{j-1} ( d[B,i,k] + d[C,k+1,j] + P_{A \Rightarrow rightarrow BC} )</tex>, то <tex>d[A,i,j]</tex> - минимальная стоимость вывода подстроки <tex>a_i...a_j</tex> из нетерминала <tex>A</tex>.
Таким образом, задача о выводе в КС-грамматике в нормальной форме Хомского является обобщением задачи динамического программирования на подотрезке.
