Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ — различия между версиями
Gaporf (обсуждение | вклад) м (→Контекстно-свободная грамматика: тире) |
|||
Строка 1: | Строка 1: | ||
+ | {| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;" | ||
+ | |+ | ||
+ | |-align="center" | ||
+ | |'''НЕТ ВОЙНЕ''' | ||
+ | |-style="font-size: 16px;" | ||
+ | | | ||
+ | 24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. | ||
+ | |||
+ | Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. | ||
+ | |||
+ | Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. | ||
+ | |||
+ | Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. | ||
+ | |||
+ | ''Антивоенный комитет России'' | ||
+ | |-style="font-size: 16px;" | ||
+ | |Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению. | ||
+ | |-style="font-size: 16px;" | ||
+ | |[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки]. | ||
+ | |} | ||
+ | |||
{{Задача | {{Задача | ||
|definition = | |definition = |
Версия 08:38, 1 сентября 2022
НЕТ ВОЙНЕ |
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России |
Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению. |
meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки. |
Задача: |
Пусть дана контекстно-свободная грамматика в нормальной форме Хомского и слово . Требуется выяснить, выводится ли это слово в данной грамматике. |
Содержание
Контекстно-свободная грамматика
Определение: |
Контекстно-свободная грамматика (КС-грамматика, бесконтекстная грамматика) — способ описания формального языка, представляющий собой четверку
, где:
|
Пример
Терминалы
.Нетерминалы
.Правила вывода
:
Данная грамматика задает язык правильных скобочных последовательностей. Например, последовательность может быть выведена следующим образом:
Нормальная форма Хомского
Нормальная форма Хомского — нормальная форма КС-грамматик, в которой все продукции имеют вид:
- , где — нетерминал, а — терминал
- , где , , — нетерминалы, причем и не являются начальными нетерминалами
- , где — начальный нетерминал и — пустая строка (данная продукция необходима, если в языке присуствует пустая строка)
Можно показать, что любую КС-грамматику можно привести к нормальной форме Хомского.
Алгоритм
Алгоритм Кока-Янгера-Касами (англ. Cocke-Younger-Kasami algorithm, англ. CYK-алгоритм) — алгоритм, позволяющий по слову узнать, выводимо ли оно в заданной КС-грамматике в нормальной форме Хомского. Любую КС-грамматику можно привести к НФХ, поэтому алгоритм является универсальным для любой КС-грамматики.
Будем решать задачу динамическим программированием. Дана строка размером . Заведем для неё трехмерный массив размером , состоящий из логических значений, и тогда и только тогда, когда из нетерминала правилами грамматики можно вывести подстроку .
Рассмотрим все пары
, где — константа и .- . Инициализируем массив для всех нетерминалов, из которых выводится какой-либо символ строки . В таком случае , если в грамматике присутствует правило . Иначе .
- . Значения для всех нетерминалов и пар уже вычислены, поэтому . То есть, подстроку можно вывести из нетерминала , если существует продукция вида и такое , что подстрока выводима из , а подстрока выводится из .
После окончания работы значение
содержит ответ на вопрос, выводима ли данная строка в данной грамматике, где — начальный символ грамматики.Модификации
Количество способов вывести слово
Если массив будет хранить целые числа, а формулу заменить на
, то — количество способов получить подстроку из нетерминала .Минимальная стоимость вывода слова
Пусть
— стоимость вывода по правилу . Тогда, если использовать формулу , то — минимальная стоимость вывода подстроки из нетерминала .Таким образом, задача о выводе в КС-грамматике в нормальной форме Хомского является частным случаем задачи динамического программирования на подотрезке.
Асимптотика
Обработка правил вида
выполняется за .Проход по всем подстрокам выполняется за
. В обработке одной подстроки присутствует цикл по всем правилам вывода и по всем разбиениям на две подстроки, следовательно обработка работает за . В итоге получаем конечную сложность .Следовательно, общее время работы алгоритма — нетерминалов грамматики.
. Кроме того, алгоритму требуется память на массив объемом , где — количествоПример работы
Дана грамматика правильных скобочных последовательностей в нормальной форме Хомского.
Дано слово
.
Инициализация массива .
A | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ||||||
2 | ||||||
3 | ||||||
4 | ||||||
5 | ||||||
6 |
B | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ||||||
2 | ||||||
3 | ||||||
4 | ||||||
5 | ||||||
6 |
C | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ● | |||||
2 | ||||||
3 | ● | |||||
4 | ● | |||||
5 | ||||||
6 |
D | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ||||||
2 | ● | |||||
3 | ||||||
4 | ||||||
5 | ● | |||||
6 | ● |
E | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ||||||
2 | ● | |||||
3 | ||||||
4 | ||||||
5 | ● | |||||
6 | ● |
Заполнение массива
.
Итерация .
A | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ● | |||||
2 | ||||||
3 | ||||||
4 | ● | |||||
5 | ||||||
6 |
B | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ● | |||||
2 | ||||||
3 | ||||||
4 | ● | |||||
5 | ||||||
6 |
C | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ● | |||||
2 | ||||||
3 | ● | |||||
4 | ● | |||||
5 | ||||||
6 |
D | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ||||||
2 | ● | |||||
3 | ||||||
4 | ||||||
5 | ● | |||||
6 | ● |
E | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ||||||
2 | ● | |||||
3 | ||||||
4 | ||||||
5 | ● | |||||
6 | ● |
Итерация
.A | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ● | |||||
2 | ||||||
3 | ||||||
4 | ● | |||||
5 | ||||||
6 |
B | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ● | |||||
2 | ||||||
3 | ||||||
4 | ● | |||||
5 | ||||||
6 |
C | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ● | |||||
2 | ||||||
3 | ● | |||||
4 | ● | |||||
5 | ||||||
6 |
D | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ||||||
2 | ● | |||||
3 | ||||||
4 | ● | |||||
5 | ● | |||||
6 | ● |
E | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ||||||
2 | ● | |||||
3 | ||||||
4 | ||||||
5 | ● | |||||
6 | ● |
Итерация
.A | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ● | |||||
2 | ||||||
3 | ● | |||||
4 | ● | |||||
5 | ||||||
6 |
B | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ● | |||||
2 | ||||||
3 | ● | |||||
4 | ● | |||||
5 | ||||||
6 |
C | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ● | |||||
2 | ||||||
3 | ● | |||||
4 | ● | |||||
5 | ||||||
6 |
D | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ||||||
2 | ● | |||||
3 | ||||||
4 | ● | |||||
5 | ● | |||||
6 | ● |
E | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ||||||
2 | ● | |||||
3 | ||||||
4 | ||||||
5 | ● | |||||
6 | ● |
Итерация
.A | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ● | |||||
2 | ||||||
3 | ● | |||||
4 | ● | |||||
5 | ||||||
6 |
B | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ● | |||||
2 | ||||||
3 | ● | |||||
4 | ● | |||||
5 | ||||||
6 |
C | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ● | |||||
2 | ||||||
3 | ● | |||||
4 | ● | |||||
5 | ||||||
6 |
D | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ||||||
2 | ● | |||||
3 | ||||||
4 | ● | |||||
5 | ● | |||||
6 | ● |
E | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ||||||
2 | ● | |||||
3 | ||||||
4 | ||||||
5 | ● | |||||
6 | ● |
Итерация
.A | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ● | ● | ||||
2 | ||||||
3 | ● | |||||
4 | ● | |||||
5 | ||||||
6 |
B | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ● | ● | ||||
2 | ||||||
3 | ● | |||||
4 | ● | |||||
5 | ||||||
6 |
C | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ● | |||||
2 | ||||||
3 | ● | |||||
4 | ● | |||||
5 | ||||||
6 |
D | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ||||||
2 | ● | |||||
3 | ||||||
4 | ● | |||||
5 | ● | |||||
6 | ● |
E | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ||||||
2 | ● | |||||
3 | ||||||
4 | ||||||
5 | ● | |||||
6 | ● |