Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами

Задача о выводе в контекстно-свободной грамматике - задача о том, выводимо ли данное слово в данной контекстно-свободной грамматике. Алгоритм Кока-Янгера-Касами - алгоритм, решающий эту задачу.

Определения

Контекстно-свободная грамматика

Контекстно-свободная грамматика (КС-грамматика, бесконтекстная грамматика) — частный случай формальной грамматики, у которой левые части всех правил являются одиночными нетерминалами, то есть все её продукции имеют вид L → R, где L - нетерминал, а R - последовательность терминалов и нетерминалов.

Другими словами, для задания КС-грамматики необходимо задать:

• Множество [math]\Sigma[/math] терминальных символов
• Множество [math]N[/math] нетерминальных символов
• Стартовый нетерминал [math]S \in N[/math]
• Множество продукций вида [math]A \rightarrow B_1 B_2 ... B_n[/math], где [math]A \in N[/math], [math]B_i \in \Sigma \cup N[/math]

Пример

Терминалы: {(, )}. Нетерминалы: {S}. Продукции:

• S → SS
• S → ()
• S → (S)

Данная грамматика задает язык правильных скобочных последовательностей. Например, последовательность (()(())) может быть выведена следующим образом:

• [math] S \Rightarrow (S) \Rightarrow (SS) \Rightarrow (()(S)) \Rightarrow (()(())) [/math]

Нормальная форма Хомского

Нормальная форма Хомского - нормальная форма КС-грамматик, в которой все продукции имеют вид:

• A → a, где A - нетерминал, а a - терминал
• A → BC, где A, B, C - нетерминалы, причем B и C не являются начальными нетерминалами
• S → ε, где S - начальный нетерминал и ε - пустая строка (данная продукция необходима, если в языке присуствует пустая строка)

Можно показать, что любую КС-грамматику можно привести к нормальной форме Хомского.

Алгоритм Кока-Янгера-Касами

Алгоритм Кока-Янгера-Касами (Cocke — Younger — Kasami algorithm, CYK - алгоритм) - универсальный алгоритм, позволяющий по слову узнать, выводимо ли оно в заданной КС-грамматике в нормальной форме Хомского.

Пусть дана строка [math]a_1 a_2 ... a_n[/math]. Заведем трехмерный массив d, состоящий из логических значений, и [math]d[A,i,j] = true[/math] тогда и только тогда, когда из нетерминала [math]A[/math] правилами грамматики можно вывести подстроку [math]a_i a_{i+1} ... a_j[/math]. Тогда:

• [math]d[A,i,i] = true[/math], если в грамматике присутствует правило [math]A \rightarrow a_i[/math], иначе [math]false[/math]
• Остальные элементы массива заполняются динамически: [math]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][/math]. То есть, подстроку [math]a_i...a_j[/math] можно вывести из нетерминала [math]A[/math], если существует продукция [math]A \rightarrow BC[/math] и такое [math]k[/math], что подстрока [math]a_i...a_k[/math] выводима из [math]B[/math], а подстрока [math]a_{k+1}...a_j[/math] - из [math]C[/math].

Значение [math]d[S,1,n][/math] содержит ответ на вопрос, выводима ли данная строка в данной грамматике.

Заметим, что если массив будет хранить целые числа, а формулу заменить на [math]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][/math], то [math]d[A,i,j][/math] - количество способов получить подстроку [math]a_i...a_j[/math] из нетерминала [math]A[/math].

Пусть [math]P_{A \rightarrow BC}[/math] - стоимость вывода по правилу [math]A \rightarrow BC[/math]. Тогда, если использовать формулу [math]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} )[/math], то [math]d[A,i,j][/math] - минимальная стоимость вывода подстроки [math]a_i...a_j[/math] из нетерминала [math]A[/math].

Таким образом, задача о выводе в КС-грамматике в нормальной форме Хомского является обобщением задачи динамического программирования на подотрезке.

Сложность алгоритма

Пусть, [math]n[/math] - длина входной строки, а [math]m[/math] - количество правил вывода в грамматике.

Обработка правил вида [math]A \rightarrow a_i[/math] выполняется за [math]O(nm)[/math].

Проход по всем подстрокам выполняется за [math]O(n^2)[/math]. В обработке подстроки присутствует цикл по всем правилам вывода и по всем разбиениям на две подстроки, следовательно обработка работает за [math]O(nm)[/math]. В итоге - [math]O(n^3 m)[/math].

Следовательно, общее время работы алгоритма - [math]O(n^3 m)[/math]. Кроме того, алгоритму требуется память (на массив [math]d[/math]) объемом [math]O(n^2 m)[/math].

Псевдокод

 funtion CYK (a - строка длины n, G - набор правил вывода грамматики с m нетерминалами, S - стартовый нетерминал) -> bool
 begin
   d : array [1..m,1..n,1..n] of bool
   for i = 1 to n
     if (A -> a[i] - продукция)
       d[A,i,i] = true
   for len = 1 to n-1
     for i = 1 to n-l
       for (A -> BC - продукция)
         for k = i to i+len-1
           d[A,i,i+len] = d[A,i,i+len] or (d[B,i,k] and d[C,k+1,i+len])
   return d[S,1,n]
 end

Ссылки

• Википедия - CYK algorithm
• Алгоритм Кока-Янгера-Касами