Изменения

'''Алгоритм Кока-Янгера-Касами''' (англ. ''Cocke — -Younger — -Kasami algorithm'', 'англ. ''CYK - алгоритм''') {{-- -}} универсальный алгоритм, позволяющий по слову узнать, выводимо ли оно в заданной КС-грамматике в нормальной форме Хомского.Будем решать задачу [[Динамическое_программирование|динамическим программированием]]. Дана строка <tex>w</tex> размером <tex>n</tex>. Заведем для неё трехмерный массив <tex>d</tex> размером <tex>|\Gamma| \times n \times n</tex>, состоящий из логических значений, и <tex>d[A][i][j] = true</tex> тогда и только тогда, когда из нетерминала <tex>A</tex> правилами грамматики можно вывести подстроку <tex>w[i \dots j]</tex>.

Рассмотрим все пары <tex>\lbrace \langle j, i \rangle | j-i=m \rbrace</tex>, где <tex>m</tex> {{- --}} константа и <tex>m < n</tex>. <tex>|w| = n</tex>.

* <tex>i === Шаг 1j</tex>. База ===Инициализируем массив для всех нетерминалов, из которых выводится какой-либо символ строки <tex>m = 0w</tex>. В таком случае <tex>d[A][i ][i] = jtrue</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' <tex>wm \rbrace</tex>. В таком случае:: уже вычислены, поэтому <tex>d[A][i][j] = \bigvee\limits_{A \rightarrow BC}\bigvee\limits_{k = i}^{j-1} d[B][i] = true[k] \wedge d[C][k+1][j]</tex>. То есть, если в грамматике подстроку <tex>w[i \Gammadots j]</tex> можно вывести из нетерминала <tex>A</tex> присутствует правило , если существует продукция вида <tex>A \rightarrow BC</tex> и такое <tex>k</tex>, что подстрока <tex>w[i\dots k]</tex>. Иначе выводима из <tex>B</tex>, а подстрока <tex>dw[Ak + 1 \dots j][i][i] = false</tex> выводится из <tex>C</tex>.[[Файл:CYK_rule_2.jpg|400px]]

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

Пусть <tex>P(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] + P(A \rightarrow BC) )</tex>, то <tex>d[A][i][j]</tex> {{--- }} минимальная стоимость вывода подстроки <tex>w[i \dots j]</tex> из нетерминала <tex>A</tex>.

Следовательно, общее время работы алгоритма {{- --}} <tex>O(n^3 \cdot |\Gamma|)</tex>. Кроме того, алгоритму требуется память (на массив <tex>d</tex>) объемом <tex>O(n^2 \cdot |N|)</tex>, где <tex>|N|</tex> {{--- }} количество [[Формальные_грамматики#Определения|нетерминалов]] грамматики.