Приведение грамматики к ослабленной нормальной форме Грейбах — различия между версиями
(Холмского -> Хомского) |
|||
Строка 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=Грамматикой в '''нормальной форме Грейбах''' (англ. ''Greibach normal form'') называется [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]], в которой могут содержаться только правила одного из следующих типов: | |definition=Грамматикой в '''нормальной форме Грейбах''' (англ. ''Greibach normal form'') называется [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]], в которой могут содержаться только правила одного из следующих типов: |
Версия 07:50, 1 сентября 2022
НЕТ ВОЙНЕ |
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России |
Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению. |
meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки. |
Определение: |
Грамматикой в нормальной форме Грейбах (англ. Greibach normal form) называется контекстно-свободная грамматика, в которой могут содержаться только правила одного из следующих типов:
|
Определение: |
Грамматикой в ослабленной нормальной форме Грейбах (англ. Greibach weak normal form) называется контекстно-свободная грамматика, в которой могут содержаться только правила одного из следующих типов:
|
Содержание
Приведение грамматики к ослабленной нормальной форме Грейбах
Теорема: |
Любую контекстно-свободную грамматику можно привести к ослабленной нормальной форме Грейбах. |
Доказательство: |
Рассмотрим контекстно-свободную грамматику . Для приведения её к нормальной ослабленной форме Грейбах нужно выполнить три шага. На каждом шаге мы строим новую грамматику, допускающую тот же язык, что и .
function greibah(правилаиз контекстно-свободной грамматики ): for i = n .. 1 for j = i + 1 .. n Для каждого правила вывода из вида заменить каждое правило на . После каждой итерации главного цикла все правила для Таким образом, мы получили грамматику в ослабленной нормальной форме Грейбах, которая допускает тот же язык, что и исходная. (где ) будут иметь вид . Значит, после применения процедуры все правила грамматики будут иметь вид . |
Пример
Текущий шаг | Грамматика после применения правила |
---|---|
0. Исходная грамматика | |
1. Удаление | -правил|
2. Удаление стартового нетерминала из правых частей правил | |
3. Удаление левой рекурсии | |
4. Выполняем функцию greibah для правила | |
5. Выполняем функцию greibah для правила |
Асимптотика
Алгоритм состоит из трех шагов, сложность первого и последнего шага равны
и соответственно. Таким обзом, сложность алгоритма является , где второй член — сложность алгоритма удаления левой рекурсии.Применение
Простота доказательств
Использование нормальных форм существенно упрощает доказательство теорем. Например, использование нормальной формы Грейбах позволяет доказать, что для каждого контекстно-свободного языка (не содержащего [1]
) существует автомат с магазинной памятью без переходов по .Разбор грамматики
Нормальная форма Хомского позволяет производить разбор грамматики. Например, с помощью алгоритма Кока-Янгера-Касами. В свою очередь, нормальная форма Грейбах позволяет использовать метод рекурсивного спуска, сложность которого является линейной, несмотря на возвраты.