Изменения

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

Рассмотрим все пары <tex>a_{A\lbrace \langle j, i, \rangle | j} -i= m \begin{cases}truerbrace</tex>,&\text{$A \Rightarrow^{*} w[i..j]$;}\\false,&\text{else.}\end{cases}где <tex>m</tex> - константа и <tex>m < n</tex>.

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

*'''База'''. Инициализируем массив для всех нетерминалов, из которых выводится какой-либо символ строки <tex>m = 0w</tex>. Ячейки В таком случае:: <tex>a_{d[A, ][i, ][i}] = true</tex> заполняются значением , если в грамматике <tex>true\Gamma</tex>, если присутствует правило <tex>A \rightarrow w[i]</tex> принадлежит множеству правил . Иначе <tex>P</tex> грамматики <tex>\Gamma</tex>: <tex>a_{d[A, ][i, i} = \lbrack A \rightarrow w][i] \in P \rbrack= false</tex>.

*'''=== Шаг 2. Переход'''. Рассмотрим все пары <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>[[Файл:CYK_rule_2.jpg|thumb|300px]]

<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][Файл:CYK_rule_2j]</tex>.jpgТо есть, подстроку <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>a_{S, 1, n}</tex>, где <tex>n = |w|</tex>.Значение <tex>d[S,1,n]</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>a_i...a_j</tex> из нетерминала <tex>A</tex>. Таким образом, задача о выводе в КС-грамматике в нормальной форме Хомского является обобщением задачи динамического программирования на подотрезке.