Изменения

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

=== Описание ===Пусть <tex>a_'''Алгоритм Кока-Янгера-Касами''' (англ. ''Cocke-Younger-Kasami algorithm'', англ. ''CYK-алгоритм'') {{A---}} алгоритм, iпозволяющий по слову узнать, j} = true</tex>выводимо ли оно в заданной КС-грамматике в нормальной форме Хомского. Любую КС-грамматику можно привести к НФХ, если из нетерминала <tex>A</tex> можно вывести подстроку <tex>w[i..j]</tex>поэтому алгоритм является универсальным для любой КС-грамматики. Иначе <tex>a_{A, i, j} = false</tex>:

Будем решать задачу [[Динамическое_программирование|динамическим программированием]]. Дана строка <tex>w</tex> размером <tex>n</tex>. Заведем для неё трехмерный массив <tex>d</tex> размером <tex>|N| \times n \times n</tex>, состоящий из логических значений, и <tex>a_{d[A, ][i, ][j} ] = true \begin{cases}true</tex> тогда и только тогда,&\text{$когда из нетерминала <tex>A \Rightarrow^{*} </tex> правилами грамматики можно вывести подстроку <tex>w[i..\ldots j]$;}\\false,&\text{else.}\end{cases}</tex>.

Будем динамически заполнять матрицу Рассмотрим все пары <tex>a_{A\lbrace \langle j, i, \rangle | j}-i=m \rbrace</tex> следующим алгоритмом (индукция по , где <tex>m = j </tex> {{--- i}} константа и <tex>m < n</tex>):.

*'''База'''. <tex>m i = 0j</tex>. Ячейки <tex>a_{A, iИнициализируем массив для всех нетерминалов, i}из которых выводится какой-либо символ строки </tex> заполняются значением <tex>truew</tex>, если правило . В таком случае <tex>d[A \rightarrow w][i][i]= true \ </tex> принадлежит множеству правил , если в грамматике <tex>P\Gamma</tex> грамматики присутствует правило <tex>A \Gammarightarrow w[i]</tex>: . Иначе <tex>a_{d[A, ][i, i} = \lbrack A \rightarrow w][i] \in P \rbrack= false</tex>.

*'''Переход'''. Рассмотрим все пары <tex>\lbrace \langle j, i \rangle | ne j-i=m \rbrace</tex>. Значения для всех нетерминалов и пар <tex>\lbrace \langle j', i' \rangle | j' -i' <m \rbrace</tex> уже вычислены, так что: поэтому <tex>a_{d[A, ][i, ][j] = \bigvee\limits_{A \rightarrow BC} = \bigvee\limits_{k=i}^{j-1} d[B][i][k] \bigveewedge d[C][k+1][j] \ \ </tex>. То есть, подстроку <tex>w[i \limits_{ldots j]</tex> можно вывести из нетерминала <tex>A</tex>, если существует продукция вида <tex>A \rightarrow BC} \left( a_{B</tex> и такое <tex>k</tex>, что подстрока <tex>w[i, \ldots k} \wedge a_{C]</tex> выводима из <tex>B</tex>, а подстрока <tex>w[k+1, \ldots j} \right)]</tex> выводится из <tex>C</tex>.[[Файл:CYK_rule_2.jpg|400px]]

После окончания работы значение <tex>d[S][Файл:CYK_rule_2.jpg1][n]</tex> содержит ответ на вопрос, выводима ли данная строка в данной грамматике, где <tex>S</tex> {{---}} начальный символ грамматики.

*'''Завершение'''. После окончания работы ответ содержится в ячейке <tex>a_{S, 1, n}</tex>, где <tex>n = |w|</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 \ldots j]</tex> из нетерминала <tex>A</tex>. === Минимальная стоимость вывода слова ===Пусть <tex>H(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] + H(A \rightarrow BC) ) \ \ </tex>, то <tex>d[A][i][j]</tex> {{---}} минимальная стоимость вывода подстроки <tex>w[i \ldots j]</tex> из нетерминала <tex>A</tex>. Таким образом, задача о выводе в КС-грамматике в нормальной форме Хомского является частным случаем задачи динамического программирования на подотрезке.

Необходимо вычислить Обработка правил вида <tex>n^2A \rightarrow w[i]</tex> булевых величин. На каждую требуется затратить выполняется за <tex>O(n \cdot |P_A\Gamma|)</tex> операций. Проход по всем подстрокам выполняется за <tex>O(n^2)</tex>. В обработке одной подстроки присутствует цикл по всем правилам вывода и по всем разбиениям на две подстроки, где следовательно обработка работает за <tex>O(n \cdot |P_A\Gamma|)</tex> – количество правил. Суммируя по всем правилам В итоге получаем конечную сложность <tex>O (n^3 \cdot |\leftGamma|)</tex>. Следовательно, общее время работы алгоритма {{---}} <tex>O( n^3 \cdot |\Gamma|)</tex>. Кроме того, алгоритму требуется память на массив <tex>d</tex> объемом <tex>O(n^2 \cdot |N|)</tex>, где <tex>|N|</tex> {{---}} количество [[Формальные_грамматики#Определения|нетерминалов]] грамматики. == Пример работы ==Дана грамматика [[Правильные_скобочные_последовательности|правильных скобочных последовательностей]] <tex>\Gamma</tex> в нормальной форме Хомского. <tex>\begin{array}{l l} A \rightarrow \varepsilon\ | \rightBB\ |\ CD\\ B \rightarrow BB\ |\ CD\\ C \rightarrow (\\ D \rightarrow BE\ |\ )\\ E \rightarrow )\\\end{array}</tex> Дано слово <tex>w = ()(())</tex>.  Инициализация массива <tex>d</tex>. {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" ! colspan="7" style="background:#ffdead;"|A|-! ! 1! 2! 3! 4! 5! 6|-! 1| | | | | | |-! 2| | | | | | |-! 3| | | | | | |-! 4| | | | | | |-! 5| | | | | | |-! 6| | | | | | |}{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" ! colspan="7" style="background:#ffdead;"|B|-! ! 1! 2! 3! 4! 5! 6|-! 1| | | | | | |-! 2| | | | | | |-! 3| | | | | | |-! 4| | | | | | |-! 5| | | | | | |-! 6| | | | | | |}{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" ! colspan="7" style="background:#ffdead;"|C|-! ! 1! 2! 3! 4! 5! 6|-! 1| align="center"| ● | | | | | |-! 2| | | | | | |-! 3| | | align="center"| ● | | | |-! 4| | | | align="center"| ● | | |-! 5| | | | | | |-! 6| | | | | | |}{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" ! colspan="7" style="background:#ffdead;"|D|-! ! 1! 2! 3! 4! 5! 6|-! 1| | | | | | |-! 2| | align="center"| ● | | | | |-! 3| | | | | | |-! 4| | | | | | |-! 5| | | | | align="center"| ● | |-! 6| | | | | | align="center"| ● |}{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" ! colspan="7" style="background:#ffdead;"|E|-! ! 1! 2! 3! 4! 5! 6|-! 1| | | | | | |-! 2| | align="center"| ● | | | | |-! 3| | | | | | |-! 4| | | | | | |-! 5| | | | | align="center"| ● | |-! 6| | | | | | align="center"| ● |}<div style="clear:both;"></div> Заполнение массива <tex>d</tex>.  Итерация <tex>m = 1</tex>. {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" ! colspan="7" style="background:#ffdead;"|A|-! ! 1! 2! 3! 4! 5! 6|-! 1| | align="center"| ● | | | | |-! 2| | | | | | |-! 3| | | | | | |-! 4| | | | | align="center"| ● | |-! 5| | | | | | |-! 6| | | | | | |}{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" ! colspan="7" style="background:#ffdead;"|B|-! ! 1! 2! 3! 4! 5! 6|-! 1| | align="center"| ● | | | | |-! 2| | | | | | |-! 3| | | | | | |-! 4| | | | | align="center"| ● | |-! 5| | | | | | |-! 6| | | | | | |}{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" ! colspan="7" style="background:#ffdead;"|C|-! ! 1! 2! 3! 4! 5! 6|-! 1| align="center"| ● | | | | | |-! 2| | | | | | |-! 3| | | align="center"| ● | | | |-! 4| | | | align="center"| ● | | |-! 5| | | | | | |-! 6| | | | | | |}{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" ! colspan="7" style="background:#ffdead;"|D|-! ! 1! 2! 3! 4! 5! 6|-! 1| | | | | | |-! 2| | align="center"| ● | | | | |-! 3| | | | | | |-! 4| | | | | | |-! 5| | | | | align="center"| ● | |-! 6| | | | | | align="center"| ● |}{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" ! colspan="7" style="background:#ffdead;"|E|-! ! 1! 2! 3! 4! 5! 6|-! 1| | | | | | |-! 2| | align="center"| ● | | | | |-! 3| | | | | | |-! 4| | | | | | |-! 5| | | | | align="center"| ● | |-! 6| | | | | | align="center"| ● |}<div style="clear:both;"></div> Итерация <tex>m = 2</tex>. {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" ! colspan="7" style="background:#ffdead;"|A|-! ! 1! 2! 3! 4! 5! 6|-! 1| | align="center"| ● | | | | |-! 2| | | | | | |-! 3| | | | | | |-! 4| | | | | align="center"| ● | |-! 5| | | | | | |-! 6| | | | | | |}{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" ! colspan="7" style="background:#ffdead;"|B|-! ! 1! 2! 3! 4! 5! 6|-! 1| | align="center"| ● | | | | |-! 2| | | | | | |-! 3| | | | | | |-! 4| | | | | align="center"| ● | |-! 5| | | | | | |-! 6| | | | | | |}{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" ! colspan="7" style="background:#ffdead;"|C|-! ! 1! 2! 3! 4! 5! 6|-! 1| align="center"| ● | | | | | |-! 2| | | | | | |-! 3| | | align="center"| ● | | | |-! 4| | | | align="center"| ● | | |-! 5| | | | | | |-! 6| | | | | | |}{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" ! colspan="7" style="background:#ffdead;"|D|-! ! 1! 2! 3! 4! 5! 6|-! 1| | | | | | |-! 2| | align="center"| ● | | | | |-! 3| | | | | | |-! 4| | | | | | align="center"| ● |-! 5| | | | | align="center"| ● | |-! 6| | | | | | align="center"| ● |}{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" ! colspan="7" style="background:#ffdead;"|E|-! ! 1! 2! 3! 4! 5! 6|-! 1| | | | | | |-! 2| | align="center"| ● | | | | |-! 3| | | | | | |-! 4| | | | | | |-! 5| | | | | align="center"| ● | |-! 6| | | | | | align="center"| ● |}<div style="clear:both;"></div> Итерация <tex>m = 3</tex>.

Алгоритму требуется <tex>n^{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" ! colspan="7" style="background:#ffdead;"|A|-! ! 1! 2! 3! 4! 5! 6|-! 1| | align="center"| ● | | | | |-! 2| | | | | | |-! 3| | | | | | align="center"| ● |-! 4| | | | | align="center"| ● | |-! 5| | | | | | |-! 6| | | | | | |}{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" ! colspan="7" style="background:#ffdead;"|B|-! ! 1! 2! 3! 4! 5! 6|-! 1| | align="center"| ● | | | | |-! 2| | | | | | |-! 3| | | | | | align="center"| ● |-! 4| | | | | align="center"| ● | |-! 5| | | | | | |-! 6| | | | | | |}{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" ! colspan="7" style="background:#ffdead;"|C|-! ! 1! 2! 3! 4! 5! 6|-! 1| align="center"| ● | | | | | |-! 2| | | | | | |-! 3| | | align="center"| ● | | | |-! 4| | | | align="center"| ● | | |-! 5| | | | | | |-! 6| | | | | | |}{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" ! colspan="7" style="background:#ffdead;"|D|-! ! 1! 2! 3! 4! 5! 6|-! 1| | | | | | |-! 2| | align="center"| ● | | | | |-! 3| | | | | | |-! 4| | | | | | align="center"| ● |-! 5| | | | | align="center"| ● | |-! 6| | | | | | align="center"| ● |}{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" ! colspan="7" style="background:#ffdead;"|E|-! ! 1! 2! 3! 4! 5! 6|-! 1| | | | | | |-! 2 \cdot | | align="center"| ● | | | | |-! 3| | | | | | |-! 4| | | | | | |-! 5| |N|</tex> памяти, где <tex>| |Nalign="center"|</tex> — количество нетерминалов грамматики.● ***| Пусть, <tex>n</tex> |- длина входной строки, а ! 6| | | | | | align="center"| ● |}<texdiv style="clear:both;">m</texdiv> - количество правил вывода в грамматике.

Обработка правил вида Итерация <tex>A \rightarrow a_i</tex> выполняется за <tex>O(nm)m = 4</tex>.

Проход по всем подстрокам выполняется за <tex>O(n^{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" ! colspan="7" style="background:#ffdead;"|A|-! ! 1! 2! 3! 4! 5! 6|-! 1| | align="center"| ● | | | | |-! 2| | | | | | |-! 3| | | | | | align="center"| ● |-! 4| | | | | align="center"| ● | |-! 5| | | | | | |-! 6| | | | | | |}{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" ! colspan="7" style="background:#ffdead;"|B|-! ! 1! 2! 3! 4! 5! 6|-! 1| | align="center"| ● | | | | |-! 2| | | | | | |-! 3| | | | | | align="center"| ● |-! 4| | | | | align="center"| ● | |-! 5| | | | | | |-! 6| | | | | | |}{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" ! colspan="7" style="background:#ffdead;"|C|-! ! 1! 2! 3! 4! 5! 6|-! 1| align="center"| ● | | | | | |-! 2| | | | | | |-! 3| | | align="center"| ● | | | |-! 4| | | | align="center"| ● | | |-! 5| | | | | | |-! 6| | | | | | |}{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" ! colspan="7" style="background:#ffdead;"|D|-! ! 1! 2! 3! 4! 5! 6|-! 1| | | | | | |-! 2| | align="center"| ● | | | | |-! 3| | | | | | |-! 4| | | | | | align="center"| ● |-! 5| | | | | align="center"| ● | |-! 6| | | | | | align="center"| ● |}{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" ! colspan="7" style="background:#ffdead;"|E|-! ! 1! 2! 3! 4! 5! 6|-! 1| | | | | | |-! 2)</tex>. В обработке подстроки присутствует цикл по всем правилам вывода и по всем разбиениям на две подстроки, следовательно обработка работает за <tex>O(nm)</tex>. В итоге | | align="center"| ● | | | | |-! 3| | | | | | |-! 4| | | | | | |-! 5| | | | | align="center"| ● | |- ! 6| | | | | | align="center"| ● |}<texdiv style="clear:both;">O(n^3 m)</texdiv>.

Следовательно, общее время работы алгоритма - Итерация <tex>O(n^3 m)</tex>. Кроме того, алгоритму требуется память (на массив <tex>d</tex>) объемом <tex>O(n^2 m)= 5</tex>.