Удаление длинных правил из грамматики — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Источники информации: категория)
Строка 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 =

Версия 07:16, 1 сентября 2022

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.

Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.

Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.

Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.

Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.


Определение:
Пусть [math]\Gamma[/math]контекстно-свободная грамматика. Правило [math]A \rightarrow \beta [/math] называется длинным (англ. long rule), если [math]|\beta| \gt 2[/math].


Задача:
Пусть [math]\Gamma[/math]контекстно-свободная грамматика, содержащая длинные правила. Требуется построить эквивалентную грамматику [math]\Gamma'[/math], не содержащую длинных правил.
Задача удаления длинных правил из грамматики возникает при попытке её приведения к нормальной форме Хомского.


Алгоритм

С каждым длинным правилом [math]A \rightarrow a_1 a_2 \ldots a_k[/math], [math]k \gt 2[/math], [math]a_i \in \Sigma \cup N[/math] проделаем следующее:

  • Добавим в грамматику [math]k-2[/math] новых нетерминала [math]B_1, B_2, \ldots B_{k-2}[/math].
  • Добавим в грамматику [math]k-1[/math] новое правило:
    [math]A \rightarrow a_1B_1[/math]
    [math]B_1 \rightarrow a_2B_2[/math]
    [math]B_2 \rightarrow a_3B_3[/math]
    [math]\ldots [/math]
    [math]B_{k-2} \rightarrow a_{k-1}a_{k}[/math]
  • Удалим из грамматики правило [math]A \rightarrow a_1 a_2 \ldots a_k[/math].

Корректность алгоритма

Теорема:
Пусть [math]\Gamma[/math]контекстно-свободная грамматика. [math]\Gamma'[/math] — грамматика, полученная в результате применения алгоритма к [math]\Gamma[/math]. Тогда [math]L(\Gamma) = L(\Gamma').[/math]
Доказательство:
[math]\triangleright[/math]

[math]\Rightarrow [/math]
Покажем, что [math]L(\Gamma) \subseteq L(\Gamma')[/math].
Пусть [math]w \in L(\Gamma)[/math]. Рассмотрим вывод [math]w[/math]. Если в выводе используется длинное правило [math]A \rightarrow a_1 a_2 \ldots a_k[/math], то заменим его на последовательное применение правил [math]A \rightarrow a_1B_1[/math], [math]B_1 \rightarrow a_2B_2[/math], [math]B_2 \rightarrow a_3B_3[/math], [math]\ldots [/math], [math]B_{k-2} \rightarrow a_{k-1}a_{k}[/math]. Получим вывод [math]w[/math] в [math]\Gamma'[/math].

[math]\Leftarrow [/math]
Покажем, что [math]L(\Gamma') \subseteq L(\Gamma)[/math]. Допустим, что это не так, то есть [math]\exists w \in L(\Gamma'), w \notin L(\Gamma)[/math]. Рассмотрим вывод [math]w[/math] в [math]\Gamma' \cup \Gamma[/math], минимальный по количеству примененных правил, отсутствующих в [math]\Gamma[/math]. Найдем в этом выводе первое применение некоторого правила [math]A \rightarrow a_1A_1, a_1 \in \Sigma \cup N[/math], которого нет в [math]\Gamma[/math]. В ходе алгоритма оно было получено из некоторого длинного правила [math]A \rightarrow a_1 a_2 \ldots a_k[/math]. Применим [math]A \rightarrow a_1 a_2 \ldots a_k[/math] вместо [math]A \rightarrow a_1A_1[/math] и удалим в выводе все применения правил, полученных из [math]A \rightarrow a_1 a_2 \ldots a_k[/math].

Получим вывод [math]w[/math] в [math]\Gamma \cup \Gamma'[/math], в котором меньше применений правил, отсутствующих в [math]\Gamma[/math], чем в исходном. Противоречие.
[math]\triangleleft[/math]

Время работы алгоритма

Здесь будем понимать под [math] | \Gamma | [/math] сумму длин правых частей правил. Данный алгоритм добавляет в грамматику [math]O(\left| \Gamma \right|)[/math] новых нетерминалов, [math]O(\left| \Gamma \right|)[/math] новых правил длины [math]O(1)[/math] и, следовательно, работает за [math]O(\left| \Gamma \right|)[/math].

Пример работы

Покажем, как описанный алгоритм будет работать на следующей грамматике:

[math]S \rightarrow AB[/math]
[math]A \rightarrow aBcB[/math]
[math]B \rightarrow def[/math].

Для правила [math]A \rightarrow aBcB[/math] вводим [math] 2 [/math] новых нетерминала [math]A_1, A_2[/math] и [math] 3 [/math] новых правила:

[math]A \rightarrow aA_1[/math]
[math]A_1 \rightarrow BA_2[/math]
[math]A_2 \rightarrow cB[/math].

Для правила [math]B \rightarrow def[/math] вводим [math] 1 [/math] новый нетерминал [math]B_1[/math] и [math] 2 [/math] новых правила:

[math]B \rightarrow dB_1[/math]
[math]B_1 \rightarrow ef[/math].

В итоге полученная грамматика [math]\Gamma'[/math] будет иметь вид:

[math]S \rightarrow AB[/math]
[math]A \rightarrow aA_1[/math]
[math]A_1 \rightarrow BA_2[/math]
[math]A_2 \rightarrow cB[/math]
[math]B \rightarrow dB_1[/math]
[math]B_1 \rightarrow ef[/math].

См. также

Источники информации

  • Michael Sipser Introduction to the Theory of Computation. — PWS Publishing, 1997. — ISBN 0-534-94728-X. (с 107.)
  • Michael A. Harrison Introduction to Formal Language Theory. — Addison-Wesley, 1978. — ISBN 978-0201029550. (с 103.)
  • Wikipedia — Chomsky normal form