Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами — различия между версиями
Lis (обсуждение | вклад) (→Ссылки) |
Kabanov (обсуждение | вклад) м (Перенаправление на Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ) |
||
(не показано 20 промежуточных версий 2 участников) | |||
Строка 1: | Строка 1: | ||
− | '''Задача о выводе в контекстно-свободной грамматике''' - задача о том, выводимо ли данное слово в данной контекстно-свободной грамматике. '''Алгоритм Кока-Янгера-Касами''' - алгоритм, решающий | + | #перенаправление [[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ]] |
+ | '''Задача о выводе в контекстно-свободной грамматике''' - задача о том, выводимо ли данное слово в данной контекстно-свободной грамматике. '''Алгоритм Кока-Янгера-Касами''' - алгоритм, решающий эту задачу. | ||
= Определения = | = Определения = | ||
− | == | + | == Контекстно-свободная грамматика == |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | = | + | {{Определение |
+ | |definition= | ||
+ | '''[[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|Контекстно-свободная грамматика]]''' ('''КС-грамматика''', '''бесконтекстная грамматика''') — способ описания формального языка, задающийся: | ||
− | + | * Множеством <tex>\Sigma</tex> терминальных символов | |
+ | * Множеством <tex>N</tex> нетерминальных символов | ||
+ | * Стартовым нетерминалом <tex>S \in N</tex> | ||
+ | * Множеством продукций вида <tex>A \rightarrow B_1 B_2 ... B_n</tex>, где <tex>A \in N</tex>, <tex>B_i \in \Sigma \cup N</tex>, то есть у которых левые части - одиночные нетерминалы, а правые - последовательности терминалов и нетерминалов. | ||
+ | }} | ||
=== Пример === | === Пример === | ||
Строка 45: | Строка 23: | ||
* S → (S) | * S → (S) | ||
− | + | Данная грамматика задает язык правильных скобочных последовательностей. Например, последовательность (()(())) может быть выведена следующим образом: | |
− | * S | + | * <tex> S \Rightarrow (S) \Rightarrow (SS) \Rightarrow (()(S)) \Rightarrow (()(())) </tex> |
== Нормальная форма Хомского == | == Нормальная форма Хомского == | ||
Строка 55: | Строка 33: | ||
* S → ε, где S - начальный нетерминал и ε - пустая строка (данная продукция необходима, если в языке присуствует пустая строка) | * S → ε, где S - начальный нетерминал и ε - пустая строка (данная продукция необходима, если в языке присуствует пустая строка) | ||
− | Можно показать, что любую КС-грамматику можно привести к нормальной форме Хомского. | + | [[Нормальная форма Хомского|Можно показать]], что любую КС-грамматику можно привести к нормальной форме Хомского. |
= Алгоритм Кока-Янгера-Касами = | = Алгоритм Кока-Янгера-Касами = | ||
'''Алгоритм Кока-Янгера-Касами''' (''Cocke — Younger — Kasami algorithm'', '''CYK - алгоритм''') - универсальный алгоритм, позволяющий по слову узнать, выводимо ли оно в заданной КС-грамматике в нормальной форме Хомского. | '''Алгоритм Кока-Янгера-Касами''' (''Cocke — Younger — Kasami algorithm'', '''CYK - алгоритм''') - универсальный алгоритм, позволяющий по слову узнать, выводимо ли оно в заданной КС-грамматике в нормальной форме Хомского. | ||
− | Пусть дана строка <tex>a_1 a_2 ... a_n</tex>. Заведем трехмерный массив d, состоящий из логических значений, и <tex>d[A | + | Пусть дана строка <tex>a_1 a_2 ... a_n</tex>. Заведем трехмерный массив d, состоящий из логических значений, и <tex>d[A,i,j] = true</tex> тогда и только тогда, когда из нетерминала <tex>A</tex> правилами грамматики можно вывести подстроку <tex>a_i a_{i+1} ... a_j</tex>. Тогда: |
− | * <tex>d[A | + | * <tex>d[A,i,i] = true</tex>, если в грамматике присутствует правило <tex>A \rightarrow a_i</tex>, иначе <tex>false</tex> |
− | * Остальные элементы массива заполняются динамически: <tex>d[A | + | * Остальные элементы массива заполняются динамически: <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>a_i...a_j</tex> можно вывести из нетерминала <tex>A</tex>, если существует продукция <tex>A \rightarrow BC</tex> и такое <tex>k</tex>, что подстрока <tex>a_i...a_k</tex> выводима из <tex>B</tex>, а подстрока <tex>a_{k+1}...a_j</tex> - из <tex>C</tex>. |
− | Значение <tex>d[S | + | Значение <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>a_i...a_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>. | |
− | + | Таким образом, задача о выводе в КС-грамматике в нормальной форме Хомского является обобщением задачи динамического программирования на подотрезке. | |
− | + | === Сложность алгоритма === | |
+ | |||
+ | Пусть, <tex>n</tex> - длина входной строки, а <tex>m</tex> - количество правил вывода в грамматике. | ||
+ | |||
+ | Обработка правил вида <tex>A \rightarrow a_i</tex> выполняется за <tex>O(nm)</tex>. | ||
− | + | Проход по всем подстрокам выполняется за <tex>O(n^2)</tex>. В обработке подстроки присутствует цикл по всем правилам вывода и по всем разбиениям на две подстроки, следовательно обработка работает за <tex>O(nm)</tex>. В итоге - <tex>O(n^3 m)</tex>. | |
− | + | Следовательно, общее время работы алгоритма - <tex>O(n^3 m)</tex>. Кроме того, алгоритму требуется память (на массив <tex>d</tex>) объемом <tex>O(n^2 m)</tex>. | |
− | |||
− | |||
− | |||
− | + | === Псевдокод === | |
− | |||
− | |||
− | + | function CYK (a - строка длины n, G - набор правил вывода грамматики с m нетерминалами, S - стартовый нетерминал) -> bool | |
− | for i = 1 to n | + | begin |
− | + | d : array [1..m,1..n,1..n] of bool | |
− | d[ | + | for i = 1 to n |
− | for k = i to i+ | + | 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 | ||
= Ссылки = | = Ссылки = | ||
Строка 96: | Строка 80: | ||
* [http://en.wikipedia.org/wiki/CYK_algorithm Википедия - CYK algorithm] | * [http://en.wikipedia.org/wiki/CYK_algorithm Википедия - CYK algorithm] | ||
* [http://www.ctc.msiu.ru/program/t-system/diploma/node39.html Алгоритм Кока-Янгера-Касами] | * [http://www.ctc.msiu.ru/program/t-system/diploma/node39.html Алгоритм Кока-Янгера-Касами] | ||
+ | |||
+ | [[Категория:В разработке]] | ||
+ | [[Категория:Дискретная математика и алгоритмы]] | ||
+ | [[Категория:Динамическое программирование]] | ||
+ | [[Категория:Теория формальных языков]] |
Текущая версия на 23:24, 4 ноября 2014
Перенаправление на:
Задача о выводе в контекстно-свободной грамматике - задача о том, выводимо ли данное слово в данной контекстно-свободной грамматике. Алгоритм Кока-Янгера-Касами - алгоритм, решающий эту задачу.
Содержание
Определения
Контекстно-свободная грамматика
Определение: |
Контекстно-свободная грамматика (КС-грамматика, бесконтекстная грамматика) — способ описания формального языка, задающийся:
|
Пример
Терминалы: {(, )}. Нетерминалы: {S}. Продукции:
- S → SS
- S → ()
- S → (S)
Данная грамматика задает язык правильных скобочных последовательностей. Например, последовательность (()(())) может быть выведена следующим образом:
Нормальная форма Хомского
Нормальная форма Хомского - нормальная форма КС-грамматик, в которой все продукции имеют вид:
- A → a, где A - нетерминал, а a - терминал
- A → BC, где A, B, C - нетерминалы, причем B и C не являются начальными нетерминалами
- S → ε, где S - начальный нетерминал и ε - пустая строка (данная продукция необходима, если в языке присуствует пустая строка)
Можно показать, что любую КС-грамматику можно привести к нормальной форме Хомского.
Алгоритм Кока-Янгера-Касами
Алгоритм Кока-Янгера-Касами (Cocke — Younger — Kasami algorithm, CYK - алгоритм) - универсальный алгоритм, позволяющий по слову узнать, выводимо ли оно в заданной КС-грамматике в нормальной форме Хомского.
Пусть дана строка
. Заведем трехмерный массив d, состоящий из логических значений, и тогда и только тогда, когда из нетерминала правилами грамматики можно вывести подстроку . Тогда:- , если в грамматике присутствует правило , иначе
- Остальные элементы массива заполняются динамически: . То есть, подстроку можно вывести из нетерминала , если существует продукция и такое , что подстрока выводима из , а подстрока - из .
Значение
содержит ответ на вопрос, выводима ли данная строка в данной грамматике.Заметим, что если массив будет хранить целые числа, а формулу заменить на
, то - количество способов получить подстроку из нетерминала .Пусть
- стоимость вывода по правилу . Тогда, если использовать формулу , то - минимальная стоимость вывода подстроки из нетерминала .Таким образом, задача о выводе в КС-грамматике в нормальной форме Хомского является обобщением задачи динамического программирования на подотрезке.
Сложность алгоритма
Пусть,
- длина входной строки, а - количество правил вывода в грамматике.Обработка правил вида
выполняется за .Проход по всем подстрокам выполняется за
. В обработке подстроки присутствует цикл по всем правилам вывода и по всем разбиениям на две подстроки, следовательно обработка работает за . В итоге - .Следовательно, общее время работы алгоритма -
. Кроме того, алгоритму требуется память (на массив ) объемом .Псевдокод
function 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