Нормальная форма Хомского - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:17:09Z

rollbackEdits.php mass rollback

185.86.148.90 в 05:42, 1 сентября 2022

2022-09-01T05:42:58Z

KK: /* Источники информации */

2015-12-21T18:38:01Z

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

KK: /* Приведение грамматики к нормальной форме Хомского */

2015-12-20T19:26:26Z

‎Приведение грамматики к нормальной форме Хомского

KK: /* Пример */

2015-12-20T10:57:08Z

‎Пример

KK в 10:34, 20 декабря 2015

2015-12-20T10:34:45Z

KK: /* Пример */

2015-12-20T10:10:44Z

‎Пример

KK: /* Пример */

2015-12-20T10:06:09Z

‎Пример

KK: /* Пример */

2015-12-20T10:05:09Z

‎Пример

KK: /* Пример */

2015-12-20T10:03:01Z

‎Пример

← Предыдущая		Версия 16:17, 4 сентября 2022
Строка 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=Грамматикой в '''нормальной форме Хомского''' (англ. ''Chomsky normal form'') называется [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора\|контекстно-свободная грамматика]], в которой могут содержаться правила только следующего вида:		\|definition=Грамматикой в '''нормальной форме Хомского''' (англ. ''Chomsky normal form'') называется [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора\|контекстно-свободная грамматика]], в которой могут содержаться правила только следующего вида:

← Предыдущая		Версия 05:42, 1 сентября 2022
Строка 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=Грамматикой в '''нормальной форме Хомского''' (англ. ''Chomsky normal form'') называется [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора\|контекстно-свободная грамматика]], в которой могут содержаться правила только следующего вида:		\|definition=Грамматикой в '''нормальной форме Хомского''' (англ. ''Chomsky normal form'') называется [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора\|контекстно-свободная грамматика]], в которой могут содержаться правила только следующего вида:

@@ Строка 75: / Строка 75: @@
 ==Источники информации==
 * [[wikipedia:en:Chomsky normal form | Wikipedia {{---}} Chomsky normal form]]
-* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 280с. : ISBN 5-8459-0261-4 (рус.)
+* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528с. : ISBN 5-8459-0261-4 (рус.)

@@ Строка 30: / Строка 30: @@
 Таким образом, мы получили грамматику в нормальной форме Хомского, которая допускает тот же язык, что и <tex> \Gamma </tex>.
-Стоит заметить, что порядок выполнения операций важен. Первое правило должно быть выполнено перед вторым, иначе время нормализации ухудшится до <tex>O(2^{\left| \Gamma \right|})</tex>. Третье правило идет после второго, потому что после удаления <tex>\varepsilon</tex>-правил, могут образоваться новые цепные правила. Также четвертое правило должно быть выполнено позже третьего, так как оно может порождать бесполезные символы.
+Стоит заметить, что порядок выполнения операций важен. Первое правило должно быть выполнено перед вторым, иначе время нормализации ухудшится до <tex>O(2^{\left| \Gamma \right|})</tex>. Третье правило идет после второго, потому что после удаления <tex>\varepsilon</tex>-правил, могут образоваться новые цепные правила. Также четвертое правило должно быть выполнено позже третьего и второго, так как они могут порождать бесполезные символы.
 При таком порядке действий размеры грамматики возрастают полиномиально.

@@ Строка 64: / Строка 64: @@
 |-
 |''5. Уберём ситуации, когда в правиле встречаются несколько терминалов.''
-|<tex>S\rightarrow S_{2}S_{1}</tex><br> <tex>X\rightarrow S_{2}Y|X_{1}Y</tex><br> <tex>Y\rightarrow S_{2}Y|X_{1}Y|Y_{1}Y_{1}</tex> <br> <tex>S_{1}\rightarrow XS_{2}|S_{3}X|y</tex> <br> <tex>S_{2}\rightarrow S_{3}X|y</tex>  <br> <tex>S_{2}\rightarrow a</tex> <br> <tex>S_{3}\rightarrow y</tex> <br> <tex>X_{1}\rightarrow b</tex>  <br> <tex>Y_{1}\rightarrow c</tex>
+|<tex>S\rightarrow S_{3}S_{1}</tex><br> <tex>X\rightarrow S_{3}Y|X_{1}Y</tex> <br> <tex>Y\rightarrow S_{3}Y|X_{1}Y|Y_{1}Y_{1}</tex> <br> <tex>S_{1}\rightarrow XS_{2}|S_{4}X|y</tex> <br> <tex>S_{2}\rightarrow S_{4}X|y</tex>  <br> <tex>S_{3}\rightarrow a</tex> <br> <tex>S_{4}\rightarrow y</tex> <br> <tex>X_{1}\rightarrow b</tex>  <br> <tex>Y_{1}\rightarrow c</tex>
 |}
 <div style="clear:both;"></div>

@@ Строка 1: / Строка 1: @@
 {{Определение
 |definition=Грамматикой в '''нормальной форме Хомского''' (англ. ''Chomsky normal form'') называется [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]], в которой могут содержаться правила только следующего вида:
-<tex>A \rightarrow B C </tex>,
+:<tex>A \rightarrow B C </tex>,
-<tex>A \rightarrow a </tex>,
+:<tex>A \rightarrow a </tex>,
-<tex>S \rightarrow \varepsilon </tex>,
+:<tex>S \rightarrow \varepsilon </tex>,
 где <tex> a </tex> {{---}} терминал, <tex> A, B, C </tex> {{---}} нетерминалы, <tex> S </tex> {{---}} стартовая вершина, <tex> \varepsilon </tex> {{---}} пустая строка, стартовая вершина не содержится в правых частях правил.

@@ Строка 45: / Строка 45: @@
 == Пример ==
 {| border="1" class="wikitable" style="width: 500px; height: 500px; float: left;"
-!style="background:#f2f2f2"|Текущий шаг
+!style="background:#41aef0"|Текущий шаг
-!style="background:#f2f2f2"|Грамматика после применения правила
+!style="background:#41aef0"|Грамматика после применения правила
 |-
 |''0. Исходная грамматика''

@@ Строка 44: / Строка 44: @@
 == Пример ==
-{| border="1" class="wikitable" style="width: 600px; height: 600px; float: left;"
+{| border="1" class="wikitable" style="width: 900px; height: 900px; float: left;"
 !style="background:#f2f2f2"|Текущий шаг
 !style="background:#f2f2f2"|Грамматика после применения правила
 |-
-|style="background:#ffffff"|''0. Исходная грамматика''
+|''0. Исходная грамматика''
-|style="background:#ffffff"|<tex>S\rightarrow aXbX|aZ</tex> <br> <tex>X\rightarrow aY|bY|\varepsilon</tex> <br> <tex>Y\rightarrow X|cc</tex><br> <tex>Z\rightarrow ZX</tex>
+|<tex>S\rightarrow aXbX|aZ</tex> <br> <tex>X\rightarrow aY|bY|\varepsilon</tex> <br> <tex>Y\rightarrow X|cc</tex><br> <tex>Z\rightarrow ZX</tex>
 |-
-|style="background:#ffffff"|''1. Удаление длинных правил''
+|''1. Удаление длинных правил''
-|style="background:#ffffff"|<tex>S\rightarrow aS_{1}|aZ</tex> <br> <tex>X\rightarrow aY|bY|\varepsilon</tex> <br> <tex>Y\rightarrow X|cc</tex> <br> <tex>Z\rightarrow ZX</tex> <br> <tex>S_{1}\rightarrow XS_{2}</tex> <br> <tex>S_{2}\rightarrow yX</tex>
+|<tex>S\rightarrow aS_{1}|aZ</tex> <br> <tex>X\rightarrow aY|bY|\varepsilon</tex> <br> <tex>Y\rightarrow X|cc</tex> <br> <tex>Z\rightarrow ZX</tex> <br> <tex>S_{1}\rightarrow XS_{2}</tex> <br> <tex>S_{2}\rightarrow yX</tex>
 |-
-|style="background:#ffffff"|''2. Удаление <tex>\varepsilon</tex>-правил''
+|''2. Удаление <tex>\varepsilon</tex>-правил''
-|style="background:#ffffff"|<tex>S\rightarrow aS_{1}|aZ</tex><br> <tex>X\rightarrow aY|bY</tex> <br> <tex>Y\rightarrow aY|bY|cc</tex> <br> <tex>Z\rightarrow ZX</tex> <br> <tex>S_{1}\rightarrow XS_{2}|S_{2}</tex> <br> <tex>S_{2}\rightarrow yX|y</tex>
+|<tex>S\rightarrow aS_{1}|aZ</tex><br> <tex>X\rightarrow aY|bY</tex> <br> <tex>Y\rightarrow aY|bY|cc</tex> <br> <tex>Z\rightarrow ZX</tex> <br> <tex>S_{1}\rightarrow XS_{2}|S_{2}</tex> <br> <tex>S_{2}\rightarrow yX|y</tex>
 |-
-|style="background:#ffffff"|''3. Удаление цепных правил''
+|''3. Удаление цепных правил''
-|style="background:#ffffff"|<tex>S\rightarrow aS_{1}|aZ</tex><br> <tex>X\rightarrow aY|bY</tex> <br> <tex>Y\rightarrow aY|bY|cc</tex> <br> <tex>Z\rightarrow ZX</tex> <br> <tex>S_{1}\rightarrow XS_{2}|yX|y</tex> <br> <tex>S_{2}\rightarrow yX|y</tex>
+|<tex>S\rightarrow aS_{1}|aZ</tex><br> <tex>X\rightarrow aY|bY</tex> <br> <tex>Y\rightarrow aY|bY|cc</tex> <br> <tex>Z\rightarrow ZX</tex> <br> <tex>S_{1}\rightarrow XS_{2}|yX|y</tex> <br> <tex>S_{2}\rightarrow yX|y</tex>
 |-
-|style="background:#ffffff"|''4. Удаление бесполезных символов''
+|''4. Удаление бесполезных символов''
-|style="background:#ffffff"|<tex>S\rightarrow aS_{1}</tex> <br> <tex>X\rightarrow aY|bY</tex> <br> <tex>Y\rightarrow aY|bY|cc</tex> <br> <tex>S_{1}\rightarrow XS_{2}|yX|y</tex> <br> <tex>S_{2}\rightarrow yX|y</tex>
+|<tex>S\rightarrow aS_{1}</tex> <br> <tex>X\rightarrow aY|bY</tex> <br> <tex>Y\rightarrow aY|bY|cc</tex> <br> <tex>S_{1}\rightarrow XS_{2}|yX|y</tex> <br> <tex>S_{2}\rightarrow yX|y</tex>
 |-
-|style="background:#ffffff"|''5. Уберём ситуации, когда в правиле встречаются несколько терминалов.''
+|''5. Уберём ситуации, когда в правиле встречаются несколько терминалов.''
-|style="background:#ffffff"|<tex>S\rightarrow S_{2}S_{1}</tex><br> <tex>X\rightarrow S_{2}Y|X_{1}Y</tex><br> <tex>Y\rightarrow S_{2}Y|X_{1}Y|Y_{1}Y_{1}</tex> <br> <tex>S_{1}\rightarrow XS_{2}|S_{3}X|y</tex> <br> <tex>S_{2}\rightarrow S_{3}X|y</tex>  <br> <tex>S_{2}\rightarrow a</tex> <br> <tex>S_{3}\rightarrow y</tex> <br> <tex>X_{1}\rightarrow b</tex>  <br> <tex>Y_{1}\rightarrow c</tex>
+|<tex>S\rightarrow S_{2}S_{1}</tex><br> <tex>X\rightarrow S_{2}Y|X_{1}Y</tex><br> <tex>Y\rightarrow S_{2}Y|X_{1}Y|Y_{1}Y_{1}</tex> <br> <tex>S_{1}\rightarrow XS_{2}|S_{3}X|y</tex> <br> <tex>S_{2}\rightarrow S_{3}X|y</tex>  <br> <tex>S_{2}\rightarrow a</tex> <br> <tex>S_{3}\rightarrow y</tex> <br> <tex>X_{1}\rightarrow b</tex>  <br> <tex>Y_{1}\rightarrow c</tex>
 |}