390
правок
Изменения
м
=== Описание ==='''Алгоритм Кока-Янгера-Касами''' (англ. ''Cocke-Younger-Kasami algorithm'', англ. ''CYK-алгоритм'') {{---}} алгоритм, позволяющий по слову узнать, выводимо ли оно в заданной КС-грамматике в нормальной форме Хомского. Любую КС-грамматику можно привести к НФХ, поэтому алгоритм является универсальным для любой КС-грамматики. Пусть Будем решать задачу [[Динамическое_программирование|динамическим программированием]]. Дана строка <tex>a_{w</tex> размером <tex>n</tex>. Заведем для неё трехмерный массив <tex>d</tex> размером <tex>|N| \times n \times n</tex>, состоящий из логических значений, и <tex>d[A, ][i, ][j} ] = true\ </tex>тогда и только тогда, если когда из нетерминала <tex>A</tex> правилами грамматики можно вывести подстроку <tex>w[i..\ldots j]</tex>. Иначе Рассмотрим все пары <tex>a_{A\lbrace \langle j, i\rangle | j-i=m \rbrace</tex>, jгде <tex>m</tex> {{---}} = falseконстанта и <tex>m < n</tex>:.
Будем динамически заполнять матрицу * <tex>a_i \ne j</tex>. Значения для всех нетерминалов и пар <tex>\lbrace \langle j', i' \rangle | j' - i' < m \rbrace</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>m = w[i \ldots j - ]</tex> можно вывести из нетерминала <tex>A</tex>, если существует продукция вида <tex>A \rightarrow BC</tex> и такое <tex>k</tex>, что подстрока <tex>w[i\ldots k]</tex> выводима из <tex>B</tex>, а подстрока <tex>w[k + 1 \ldots j]</tex> выводится из <tex>C</tex>).[[Файл:CYK_rule_2.jpg|400px]]
*'''База'''. После окончания работы значение <tex>m = 0d[S][1][n]</tex>. Ячейки <tex>a_{Aсодержит ответ на вопрос, iвыводима ли данная строка в данной грамматике, i}где </tex> заполняются значением <tex>trueS</tex>, если правило <tex>A \rightarrow w[i]</tex> принадлежит множеству правил <tex>P</tex> грамматики <tex>\Gamma</tex>: <tex>a_{A, i, i{---}} = \lbrack A \rightarrow w[i] \in P \rbrack</tex>начальный символ грамматики.
*'''Переход'''. Рассмотрим все пары <tex>\lbrace \langle j, i \rangle | j-i=m \rbrace</tex>. Значения для всех нетерминалов и пар <tex>\lbrace \langle j', i' \rangle | j-i<m \rbrace</tex> уже вычислены, так что: <tex>a_{A, i, j} = \bigvee\limits_{kМодификации ==i}^{j-1} \bigvee\limits_{A \rightarrow BC} \left( a_{B, i, k} \wedge a_{C, k+1, j} \right)</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 \left( n^3 \cdot |\Gamma| \right)</tex>.
Алгоритму требуется Следовательно, общее время работы алгоритма {{---}} <tex>O(n^2 3 \cdot |N\Gamma|)</tex> памяти. Кроме того, где алгоритму требуется память на массив <tex>|N|d</tex> — количество нетерминалов грамматики.***Пусть, объемом <tex>O(n^2 \cdot |N|)</tex> - длина входной строки, а где <tex>m|N|</tex> {{- --}} количество правил вывода в грамматике[[Формальные_грамматики#Определения|нетерминалов]] грамматики.
Обработка правил вида == Пример работы ==Дана грамматика [[Правильные_скобочные_последовательности|правильных скобочных последовательностей]] <tex>A \rightarrow a_i</tex> выполняется за <tex>O(nm)Gamma</tex>в нормальной форме Хомского.
Проход по всем подстрокам выполняется за <tex>O\begin{array}{l l} A \rightarrow \varepsilon\ |\ BB\ |\ CD\\ B \rightarrow BB\ |\ CD\\ C \rightarrow (n^2\\ D \rightarrow BE\ |\ )</tex>. В обработке подстроки присутствует цикл по всем правилам вывода и по всем разбиениям на две подстроки, следовательно обработка работает за <tex>O(nm)</tex>. В итоге - <tex>O(n^3 m\\ E \rightarrow )\\\end{array}</tex>.
Следовательно, общее время работы алгоритма - Дано слово <tex>Ow = (n^3 m)</tex>. Кроме того, алгоритму требуется память (на массив <tex>d</tex>() объемом <tex>O(n^2 m)</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>. {| 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| | align="center"| ● | | | | |-! 3| | | | | | |-! 4| | | | | | |-! 5| | | | | align="center"| ● | |-! 6| | | | | | align="center"| ● |}<div style="clear:both;"></div> Итерация <tex>m = 4</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| | | | | | 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| | align="center"| ● | | | | |-! 3| | | | | | |-! 4| | | | | | |-! 5| | | | | align="center"| ● | |-! 6| | | | | | align="center"| ● |}<div style="clear:both;"></div> Итерация <tex>m = 5</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"| ● | | | | 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"| ● | | | | 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| | align="center"| ● | | | | |-! 3| | | | | | |-! 4| | | | | | |-! 5| | | | | align="center"| ● | |-! 6| | | | | | align="center"| ● |}<div style="clear:both;"></div>
→Контекстно-свободная грамматика: тире
{{Задача
|definition =
Пусть дана [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]] грамматика <tex>\Gamma</tex> в [[нормальная форма Хомского|нормальной форме Хомского]] и слово <tex>w \in \Sigma^{*}</tex>. Требуется выяснить, выводится ли это слово в данной грамматике.
}}
== Контекстно-свободная грамматика ==
{{Определение
|definition =
'''[[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|Контекстно-свободная грамматика]]''' ('''КС-грамматика''', '''бесконтекстная грамматика''') {{---}} способ описания формального языка, представляющий собой четверку
<tex>\Gamma =\langle \Sigma, N, S \in N, P \subset N^{+}\times (\Sigma\cup N)^{*}\rangle</tex>, где:
* <tex>\Sigma</tex> {{---}} [[Основные_определения: алфавит, слово, язык, конкатенация, свободный моноид слов|алфавит]], элементы которого называют '''терминалами''' (англ. ''terminals'')
* <tex>N</tex> {{---}} множество, элементы которого называют '''нетерминалами''' (англ. ''nonterminals'')
* <tex>S</tex> {{---}} начальный символ грамматики (англ. ''start symbol'')
* <tex>P</tex> {{---}} набор правил вывода (англ. ''production rules'' или ''productions'') вида <tex>A \rightarrow B_1 B_2 \ldots B_n</tex>, где <tex>A \in N</tex>, <tex>B_i \in \Sigma \cup N</tex>, то есть у которых левые части {{---}} одиночные нетерминалы, а правые {{---}} последовательности терминалов и нетерминалов.
}}
=== Пример ===
Терминалы <tex>\Sigma = \{(, )\}</tex>.
Нетерминалы <tex>N = \{S\}</tex>.
Правила вывода <tex>P</tex>:
<tex>\begin{array}{l l}
S \rightarrow \varepsilon\\
S \rightarrow SS\\
S \rightarrow (S)\\
\end{array}</tex>
Данная грамматика задает язык [[Правильные_скобочные_последовательности|правильных скобочных последовательностей]]. Например, последовательность <tex>(()(()))</tex> может быть выведена следующим образом:
<tex> S \Rightarrow (S) \Rightarrow (SS) \Rightarrow (()(S)) \Rightarrow (()(())) </tex>
== Нормальная форма Хомского ==
'''[[Нормальная форма Хомского]]''' {{---}} нормальная форма КС-грамматик, в которой все продукции имеют вид:
* <tex>A \rightarrow a</tex>, где <tex>A</tex> {{---}} нетерминал, а <tex>a</tex> {{---}} терминал
* <tex>A \rightarrow BC</tex>, где <tex>A</tex>, <tex>B</tex>, <tex>C</tex> {{---}} нетерминалы, причем <tex>B</tex> и <tex>C</tex> не являются начальными нетерминалами
* <tex>S \rightarrow \varepsilon</tex>, где <tex>S</tex> {{---}} начальный нетерминал и <tex>\varepsilon</tex> {{---}} пустая строка (данная продукция необходима, если в языке присуствует пустая строка)
[[Нормальная форма Хомского|Можно показать]], что любую КС-грамматику можно привести к нормальной форме Хомского.
== Алгоритм ==
* <tex>i = j</tex>. Инициализируем массив для всех нетерминалов, из которых выводится какой-либо символ строки <tex>a_{w</tex>. В таком случае <tex>d[A, ][i][i, j} ] = true \begin{cases}true</tex>,&если в грамматике <tex>\text{$Gamma</tex> присутствует правило <tex>A \Rightarrow^{*} rightarrow w[i]</tex>..jИначе <tex>d[A][i][i]$;}\\= false,&\text{else.}\end{cases}</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][Файл:CYK_rule_2.jpgj]</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>a_{S, 1, n{---}}минимальная стоимость вывода подстроки <tex>w[i \ldots j]</tex>, где из нетерминала <tex>n = |w|A</tex>.
== Асимптотика ==
== См. также ==
* [[Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики|Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики]]
* [[Алгоритм_Эрли|Алгоритм Эрли]]
==Источники информации==
* [[wikipedia:CYK_algorithm|Wikipedia {{---}} CYK algorithm]]
* [http://web.cs.ucdavis.edu/~rogaway/classes/120/winter12/CYK.pdf David Rodriguez-Velazquez, "The CYK Algorithm"]
* [https://www.princeton.edu/~achaney/tmve/wiki100k/docs/CYK_algorithm.html Princeton University, "The CYK Algorithm"]
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]
[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]
[[Категория: Алгоритмы разбора]]
