Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами
Задача о выводе в контекстно-свободной грамматике - задача о том, выводимо ли данное слово в данной контекстно-свободной грамматике. Алгоритм Кока-Янгера-Касами - алгоритм, решающий данную задачу.
Содержание
Определения
Контекстно-свободная грамматика
Контекстно-свободная грамматика (КС-грамматика, бесконтекстная грамматика) — частный случай формальной грамматики, у которой левые части всех правил являются одиночными нетерминалами, то есть все её продукции имеют вид 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 - начальный нетерминал и ε - пустая строка (данная продукция необходима, если в языке присуствует пустая строка)
Можно показать, что любую КС-грамматику можно привести к нормальной форме Хомского.
Алгоритм Кока-Янгера-Касами
Алгоритм Кока-Янгера-Касами (Cocke — Younger — Kasami algorithm, CYK - алгоритм) - универсальный алгоритм, позволяющий по слову узнать, выводимо ли оно в заданной КС-грамматике в нормальной форме Хомского.
Пусть дана строка
. Заведем трехмерный массив d, состоящий из логических значений, и тогда и только тогда, когда из нетерминала правилами грамматики можно вывести подстроку . Тогда:- , если в грамматике присутствует правило , иначе
- Остальные элементы массива заполняются динамически: . То есть, подстроку можно вывести из нетерминала , если существует продукция и такое , что подстрока выводима из , а подстрока - из .
Значение
содержит ответ на вопрос, выводима ли данная строка в данной грамматике.Заметим, что если массив будет хранить целые числа, а формулу динамики заменить на
, то - количество способов получить подстроку из нетерминала .Пусть
- стоимость вывода по правилу . Тогда, если использовать формулу , то - минимальная стоимость вывода подстроки из нетерминала .Таким образом, задача о выводе в КС-грамматике в нормальной форме Хомского является обобщением задачи динамического программирования на подотрезке.
Сложность алгоритма
Пусть,
- длина входной строки, а - количество правил вывода в грамматике.Псевдокод
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 l = 1 to n-1 for i = 1 to n-l for (A -> BC - правило грамматики) for k = i to i+l-1 d[A,i,i+l] = d[A,i,i+l] or (d[B,i,k] and d[C,k+1,i+l]) result = d[S,1,n] end