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

Формальная грамматика

Формальная грамматика - способ описания формального языка, то есть некоторого подмножества слов данного конечного алфавита. Выделяют порождающие грамматики, состоящие из следующих компонентов:

• 1) Множество терминальных символов (терминалов) - символов алфавита, слова над которым определяет грамматика, то есть символов, непосредственно присутствующих в словах языка.
• 2) Множество нетерминальных символов (нетерминалов) - объектов, выражающих некоторые структурные части языка, не имеющие конкретного представления как слова над алфавитом (таких, как формула или часть программы).
• 3) Множество правил вывода (продукций) - правил вида L → R, где:
  • L - непустая последовательность терминальных и нетерминальных символов, содержищий по крайней мере один нетерминал.
  • R - любая (возможно, пустая) последовательность терминальных и нетерминальных символов.
• 4) S - стартовый нетерминал.

Выводом называется последовательность строк из терминалов и нетерминалов, такая, что:

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

Существование в грамматике вывода для получения конкретного слова - критерий принадлежности слова языку, определяемому грамматикой.

Пример

Терминалы: a, b. Нетерминалы: S, A, B. Продукции:

• S → AB
• A → AB
• AB → ba
• A → a
• B → b

Слова, выводимые в данной грамматике: ab, ba, abb, bab, abbb, babb, ...

Слова, невыводимые в данной грамматике: a, b, baa, baba, ...

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

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

Пример

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

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

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

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

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

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

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

Покажем, что любую КС-грамматику можно привести к нормальной форме Хомского. Рассмотрим продукцию этой грамматики: [math]A \Rightarrow A_1 A_2 A_3 ... A_n[/math], где [math]A_i[/math] - терминалы или нетерминалы. Добавим к грамматике нетерминалы [math]B_1 ... B_n[/math], [math]C_k[/math] для таких k, что [math]A_k[/math] - нетерминал, и продукции вида

• [math]A \Rightarrow B_1[/math]
• [math]B_i \Rightarrow A_i B_{i+1}[/math] если [math]A_i[/math] - нетерминал
• [math]B_i \Rightarrow C_i B_{i+1}[/math] и [math]C_i \Rightarrow A_i[/math], если [math]A_i[/math] - терминал

Очевидно, что добавленные элементы в совокупности дают рассмотренную продукцию. Проделав данную процедуру ко всем продукциям, мы и получим нормальную форму Хомского для данной грамматики.

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

Алгоритм Кока-Янгера-Касами (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]O(n^3)[/math] (где [math]n[/math] - длина строки) и требует [math]O(n^2)[/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]a_1...a_n[/math] - входная строка. [math]A_1...A_m[/math] - нетерминалы. [math]P[i,j,k] = true[/math] если есть продукция [math]A_i \Rightarrow A_j A_k[/math]. [math]S(i,c) = true[/math] если есть продукция [math]A_i \Rightarrow c[/math] (где [math]c[/math] - терминал). [math]d[i][j,k][/math] - можно ли вывести из нетерминала [math]A_i[/math] подстроку [math]a_j...a_k[/math].

 for i = 1 to m
   for j = 1 to n
     d[i][j,j] = S(i,a[j])

 for l = 2 to n
   for i = 1 to n+1-l
     for j = 1 to m
       d[j][i,i+l-1] = false
       for k = i to i+j-2
         d[j][i,i+l-1] = d[j][i,i+l-1] or (d[j][i,k] and d[j][k+1,i+l-1])

Ссылки

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