390
правок
Изменения
м
→Контекстно-свободная грамматика: тире
* <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>, то есть у которых левые части {{---}} одиночные нетерминалы, а правые {{- --}} последовательности терминалов и нетерминалов.
}}
=== Пример ===
'''Алгоритм Кока-Янгера-Касами''' (англ. ''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 \dots 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 \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[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>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 \dots ldots j]</tex> из нетерминала <tex>A</tex>.
Таким образом, задача о выводе в КС-грамматике в нормальной форме Хомского является частным случаем задачи динамического программирования на подотрезке.
