Изменения

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

== Алгоритм Контекстно-свободная грамматика =={{Определение|definition ='''Алгоритм Кока[[Контекстно-свободные грамматики, вывод, лево-Янгераи правосторонний вывод, дерево разбора|Контекстно-Касамисвободная грамматика]]''' (''Cocke — Younger — Kasami algorithm'КС-грамматика''', '''CYK - алгоритмбесконтекстная грамматика''') {{--- универсальный алгоритм}} способ описания формального языка, позволяющий по слову узнатьпредставляющий собой четверку<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>dP</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>d\begin{array}{l l} S \rightarrow \varepsilon\\ S \rightarrow SS\\ S \rightarrow (S)\\\end{array}</tex> Данная грамматика задает язык [A[Правильные_скобочные_последовательности|правильных скобочных последовательностей]]. Например, последовательность <tex>(()(()))</tex> может быть выведена следующим образом: <tex> S \Rightarrow (S) \Rightarrow (SS) \Rightarrow (()(S)) \Rightarrow (()(())) </tex> == Нормальная форма Хомского == '''[i[Нормальная форма Хомского][j] = true''' {{---}} нормальная форма КС-грамматик, в которой все продукции имеют вид:* <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>AS</tex> правилами грамматики можно вывести подстроку {{---}} начальный нетерминал и <tex>w[i \dots j]varepsilon</tex>.{{---}} пустая строка (данная продукция необходима, если в языке присуствует пустая строка)

Рассмотрим все пары <tex>\lbrace \langle j, i \rangle [[Нормальная форма Хомского| j-i=m \rbrace</tex>Можно показать]], где <tex>m</tex> что любую КС- константа и <tex>m < n</tex>. <tex>|w| = n</tex>грамматику можно привести к нормальной форме Хомского.

=== Шаг 1. База =Алгоритм ==<tex>m = 0</tex>'''Алгоритм Кока-Янгера-Касами''' (англ. ''Cocke-Younger-Kasami algorithm'', англ. ''CYK-алгоритм'') {{---}} алгоритм, позволяющий по слову узнать, выводимо ли оно в заданной КС-грамматике в нормальной форме Хомского. В таком случае <tex>i = j</tex>Любую КС-грамматику можно привести к НФХ, поэтому алгоритм является универсальным для любой КС-грамматики.

Инициализируем массив для всех нетерминалов, из которых выводится какой-либо символ строки Будем решать задачу [[Динамическое_программирование|динамическим программированием]]. Дана строка <tex>w</tex> размером <tex>n</tex>. В таком случае:: Заведем для неё трехмерный массив <tex>d[A][i][i] = true</tex>, если в грамматике размером <tex>|N| \times n \Gammatimes n</tex> присутствует правило , состоящий из логических значений, и <tex>d[A \rightarrow w][i][j] = true \ </tex>. Иначе тогда и только тогда, когда из нетерминала <tex>d[A]</tex> правилами грамматики можно вывести подстроку <tex>w[i\ldots j][i] = false</tex>.

Рассмотрим все пары <tex>\lbrace \langle j, i \rangle | j-i=== Шаг 2m \rbrace</tex>, где <tex>m</tex> {{---}} константа и <tex>m < n</tex>. Переход ===[[Файл:CYK_rule_2.jpg|thumb|400px]]

* <tex>m i = j </tex>. Инициализируем массив для всех нетерминалов, из которых выводится какой- либо символ строки <tex>w</tex>. В таком случае <tex>d[A][i][i] = true \ </tex>, если в грамматике <tex>\Gamma</tex> присутствует правило <tex>A \rightarrow w[i]</tex>. Иначе <tex>d[A][i][i] = false</tex>.

* <tex>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>w[i \dots ldots j]</tex> можно вывести из нетерминала <tex>A</tex>, если существует продукция вида <tex>A \rightarrow BC</tex> и такое <tex>k</tex>, что подстрока <tex>w[i \dots ldots k]</tex> выводима из <tex>B</tex>, а подстрока <tex>w[k + 1 \dots ldots j]</tex> - выводится из <tex>C</tex>.[[Файл:CYK_rule_2.jpg|400px]]

=== Завершение ===После окончания работы значение <tex>d[S][1][n]</tex> содержит ответ на вопрос, выводима ли данная строка в данной грамматике, где <tex>S</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 ldots j]</tex> из нетерминала <tex>A</tex>.

Пусть <tex>PH(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] + PH(A \rightarrow BC) )\ \ </tex>, то <tex>d[A][i][j]</tex> {{--- }} минимальная стоимость вывода подстроки <tex>w[i \dots ldots j]</tex> из нетерминала <tex>A</tex>. Таким образом, задача о выводе в КС-грамматике в нормальной форме Хомского является частным случаем задачи динамического программирования на подотрезке. == Асимптотика ==Обработка правил вида <tex>A \rightarrow w[i]</tex> выполняется за <tex>O(n \cdot |\Gamma|)</tex>. Проход по всем подстрокам выполняется за <tex>O(n^2)</tex>. В обработке одной подстроки присутствует цикл по всем правилам вывода и по всем разбиениям на две подстроки, следовательно обработка работает за <tex>O(n \cdot |\Gamma|)</tex>. В итоге получаем конечную сложность <tex>O(n^3 \cdot |\Gamma|)</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\ |\ BB\ |\ 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 \rightarrow w[i]|-! ! 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> в шаге 1 выполняется за m = 3</tex>O(n \cdot . {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" ! colspan="7" style="background:#ffdead;"|\GammaA|)-! ! 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>

Проход по всем подстрокам в шаге 2 выполняется за Итерация <tex>O(n^2)</tex>. В обработке одной подстроки присутствует цикл по всем правилам вывода и по всем разбиениям на две подстроки, следовательно обработка работает за <tex>O(n \cdot |\Gamma|)</tex>. В итоге получаем конечную сложность <tex>O(n^3 \cdot |\Gamma|)m = 5</tex>.

Следовательно, общее время работы алгоритма {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" ! colspan="7" style="background:#ffdead;"|A|- <tex>O(n^! ! 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 \cdot ! 4! 5! 6|-! 1| | | | | |\Gamma|)</tex>. Кроме того, алгоритму требуется память (на массив <tex>d</tex>) объемом <tex>O(n^-! 2 \cdot | | align="center"| ● | | | | |-! 3| | | | | | |-! 4| | | | | | |-! 5| | | | | align="center"| ● | |-! 6| | | | | |Nalign="center"|)</tex>, где ● |}<texdiv style="clear:both;">|N|</texdiv> - количество [[Формальные_грамматики#Определения|нетерминалов]] грамматики.