Изменения

{{Задача|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>a_\Sigma = \{A, i(, j)\} = true</tex>, если из нетерминала <tex>A</tex> можно вывести подстроку <tex>w[i..j]</tex>. Иначе <tex>a_{A, i, j} = false</tex>:

Нетерминалы <tex>a_{A, i, j} N = \begin{cases}true,&\text{$A S\Rightarrow^{*} w[i..j]$;}\\false,&\text{else.}\end{cases}</tex>.

Будем динамически заполнять матрицу Правила вывода <tex>a_{A, i, j}P</tex> следующим алгоритмом (индукция по <tex>m = j - i</tex>):

*'''База'''. <tex>m = 0</tex>. Ячейки <tex>a_\begin{array}{A, i, il l}</tex> заполняются значением <tex>true</tex>, если правило <tex>A S \rightarrow \varepsilon\\ S \rightarrow w[i]</tex> принадлежит множеству правил <tex>P</tex> грамматики <tex>SS\Gamma</tex>: <tex>a_{A, i, i} = \lbrack A S \rightarrow w[i] (S)\\in P \rbrackend{array}</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>a_{S, 1, n}</tex>, где <tex>n = |w|</tex>.= Нормальная форма Хомского ==

== Сложность алгоритма =='''[[Нормальная форма Хомского]]''' {{---}} нормальная форма КС-грамматик, в которой все продукции имеют вид:Необходимо вычислить * <tex>n^2A \rightarrow a</tex> булевых величин. На каждую требуется затратить , где <tex>A</tex>n {{---}} нетерминал, а <tex>a</tex> {{---}} терминал* <tex>A \cdot |P_A|rightarrow BC</tex> операций, где <tex>|P_A|A</tex>, <tex>B</tex>, <tex>C</tex> {{---}} нетерминалы, причем <tex>B</tex> – количество правил. Суммируя по всем правилам получаем конечную сложность и <tex>O C</tex> не являются начальными нетерминалами* <tex>S \left( n^3 rightarrow \cdot |varepsilon</tex>, где <tex>S</tex> {{---}} начальный нетерминал и <tex>\Gamma| \right)varepsilon</tex>.{{---}} пустая строка (данная продукция необходима, если в языке присуствует пустая строка)

Алгоритму требуется <tex>n^2 \cdot [[Нормальная форма Хомского|N|</tex> памятиМожно показать]], где <tex>|N|</tex> — количество нетерминалов грамматикичто любую КС-грамматику можно привести к нормальной форме Хомского.

Недостаток алгоритма заключается == Алгоритм =='''Алгоритм Кока-Янгера-Касами''' (англ. ''Cocke-Younger-Kasami algorithm'', англ. ''CYK-алгоритм'') {{---}} алгоритм, позволяющий по слову узнать, выводимо ли оно в заданной КС-грамматике в том, что изначально нормальной форме Хомского. Любую КС-грамматику необходимо можно привести к НФХ, поэтому алгоритм является универсальным для любой КС-грамматики. Будем решать задачу [[Динамическое_программирование|динамическим программированием]]. Дана строка <tex>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>\lbrace \langle j, i \rangle | j-i=m \rbrace</tex>, где <tex>m</tex> {{---}} константа и <tex>m < n</tex>. * <tex>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 \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>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 \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>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|-! ! 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> == См. также == * [[Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики|Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики]]* [[Алгоритм_Эрли|Алгоритм Эрли]]==Источники информации==* [[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"] [[Категория:Дискретная математика и алгоритмы]][[Категория:Динамическое программирование]][[Категория: Теория формальных языков]][[Категория: Контекстно-свободные грамматики]][[Категория: Алгоритмы разбора]]