Алгоритм Эрли, доказательство оценки O(n^2) для однозначной грамматики — различия между версиями
Zernov (обсуждение | вклад) (→Алгоритм) |
|||
Строка 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 Майкл Наки]. | ||
+ | |} | ||
+ | |||
==Алгоритм== | ==Алгоритм== | ||
Для начала модифицируем [[Алгоритм Эрли|алгоритм Эрли]]. Главным отличием от базовой версии алгоритма является функция <tex>\mathtt{rulesLoop}</tex>, внутри которой мы, как и в базовой версии, просматриваем второе и третье правило, однако, в отличие от базовой версии, где при каждом изменении <tex>D_j</tex> мы просматривали весь список <tex>D_j</tex> и применяли к нему второе и третье правило, в модифицированной версии мы применяем правила внутри <tex>\mathtt{rulesLoop}</tex>, просматривая только те ситуации, которые были добавлены на предыдущей итерации цикла <tex>\mathtt{while}</tex>. | Для начала модифицируем [[Алгоритм Эрли|алгоритм Эрли]]. Главным отличием от базовой версии алгоритма является функция <tex>\mathtt{rulesLoop}</tex>, внутри которой мы, как и в базовой версии, просматриваем второе и третье правило, однако, в отличие от базовой версии, где при каждом изменении <tex>D_j</tex> мы просматривали весь список <tex>D_j</tex> и применяли к нему второе и третье правило, в модифицированной версии мы применяем правила внутри <tex>\mathtt{rulesLoop}</tex>, просматривая только те ситуации, которые были добавлены на предыдущей итерации цикла <tex>\mathtt{while}</tex>. |
Версия 08:55, 1 сентября 2022
НЕТ ВОЙНЕ |
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России |
Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению. |
meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки. |
Содержание
Алгоритм
Для начала модифицируем алгоритм Эрли. Главным отличием от базовой версии алгоритма является функция , внутри которой мы, как и в базовой версии, просматриваем второе и третье правило, однако, в отличие от базовой версии, где при каждом изменении мы просматривали весь список и применяли к нему второе и третье правило, в модифицированной версии мы применяем правила внутри , просматривая только те ситуации, которые были добавлены на предыдущей итерации цикла .
Будем рассматривать грамматику без ε-правил и бесполезных символов.
function: // Инициализация rulesLoop(0) for j = 1 .. n for = // Первое правило rulesLoop(j)
function: while for // Цикл (*) for = // Второе правило for // Цикл (**) for = // Третье правило =
Доказательство эквивалентности
В циклах, помеченных
и , просматривается не весь список , а только те ситуации, которые были добавлены на предыдущей итерации цикла . Данная модификация является корректной.- Рассмотрим цикл . Если в текущей ситуации этого цикла , то во внутреннем цикле просматривается список с меньшим индексом, в который новые ситуации больше не добавляются. Поэтому после первого просмотра этого списка будут добавлены все ситуации, удовлетворяющие условию, и больше ситуацию в цикле рассматривать не нужно. Если же , то , что возможно, только если . Тогда во внутреннем цикле не будет добавлено ни одной ситуации, так как не встречается в правых частях правил.
- Теперь рассмотрим цикл . Так как для каждой ситуации в список добавляется новая ситуация, соответствующая правилу из грамматики, а грамматика фиксирована, то после первого просмотра будут добавлены все возможные ситуации для .
Таким образом, во все списки будут добавлены ситуации, которые были бы добавлены в ходе обычного алгоритма. Очевидно, что лишних ситуаций добавлено не будет, так как в циклах
и просматривается подмножество полного списка. Значит этот алгоритм эквивалентен оригинальному.Время работы для однозначной грамматики
Лемма (1): |
в списке находится ситуаций. |
Доказательство: |
Так как грамматика фиксирована, то | количество ситуаций вида не больше некоторой константы. Таким образом, поскольку в находятся ситуации, у которых , всего в будет ситуаций.
Лемма (2): |
Пусть — однозначная КС-грамматика без непорождающих нетерминалов и — цепочка из . Тогда алгоритм Эрли пытается включить в не более одного раза, если . |
Доказательство: |
Ситуацию можно включить в только по правилам (если последний символ — терминал) и (если нетерминал). В первом случае результат очевиден. Во втором случае допустим, что включается в , когда рассматриваются две ситуации и (они различны, так как в цикле каждая ситуация из каждого списка рассматривается по одному разу). Тогда ситуация должна оказаться одновременно в и в . Таким образом, получаем:
Следовательно, |
Теорема: |
Если входная грамматика однозначна, то время выполнения алгоритма Эрли для слова длины составляет . |
Доказательство: |
Орагнизуем каждый список разбора таким образом, чтобы по любому символу , можно было за получить список тех и только тех ситуаций, содержащихся в , которые имеют вид .Время построения не зависит от входной строки.Рассмотрим .
|
См. также
Источники информации
- А. Ахо, Дж. Ульман. Теория синтакcического анализа, перевода и компиляции. Том 1. Синтакcический анализ. Издательство "Мир", Москва, 1978г., стр. 364-366