Лемма Огдена - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:07:30Z

rollbackEdits.php mass rollback

194.88.143.66 в 06:20, 1 сентября 2022

2022-09-01T06:20:56Z

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

2018-04-02T13:17:37Z

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

Vsklamm: /* Пример 2 */

2018-04-02T13:14:40Z

‎Пример 2

Vsklamm: /* Пример 1 */

2018-04-02T13:08:57Z

‎Пример 1

188.242.29.236: /* Лемма */

2018-03-13T17:55:22Z

‎Лемма

188.242.29.236: /* Пример 2 */

2018-03-03T12:39:40Z

‎Пример 2

188.242.29.236: /* Пример 1 */

2018-03-03T12:39:16Z

‎Пример 1

80.249.188.172: /* Примеры не КС-языка, для которого выполняется лемма */

2017-01-19T14:58:53Z

‎Примеры не КС-языка, для которого выполняется лемма

80.249.188.172 в 14:52, 19 января 2017

2017-01-19T14:52:35Z

← Предыдущая		Версия 16:07, 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 Майкл Наки].
−	\|}
−
	Для бесконечного языка применение приведённых в предыдущем разделе приёмов приведёт к началу построения в общем случае бесконечного числа правил грамматики. Требуется более мощный аппарат, которым служит доказываемая ниже лемма Огдена.		Для бесконечного языка применение приведённых в предыдущем разделе приёмов приведёт к началу построения в общем случае бесконечного числа правил грамматики. Требуется более мощный аппарат, которым служит доказываемая ниже лемма Огдена.

← Предыдущая		Версия 06:20, 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 Майкл Наки].
		+	\|}
		+
	Для бесконечного языка применение приведённых в предыдущем разделе приёмов приведёт к началу построения в общем случае бесконечного числа правил грамматики. Требуется более мощный аппарат, которым служит доказываемая ниже лемма Огдена.		Для бесконечного языка применение приведённых в предыдущем разделе приёмов приведёт к началу построения в общем случае бесконечного числа правил грамматики. Требуется более мощный аппарат, которым служит доказываемая ниже лемма Огдена.

@@ Строка 72: / Строка 72: @@
 == Источники информации ==
-*[http://ru.wikipedia.org/wiki/Лемма_Огдена Лемма Огдена]
+* [http://ru.wikipedia.org/wiki/Лемма_Огдена Wikipedia {{---}} Лемма Огдена]
-*Hopcroft, Motwani and Ullman  {{---}} Automata Theory, Languages, and Computation {{---}} Addison-Wesley, 1979. ISBN 81-7808-347-7.
+* ''Hopcroft, Motwani and Ullman''  {{---}} Automata Theory, Languages, and Computation {{---}} Addison-Wesley, 1979. ISBN 81-7808-347-7.
-*Ogden, W. (1968). "A helpful result for proving inherent ambiguity". Mathematical Systems Theory. 2 (3): 191–194.
+* ''Ogden, W.'' (1968). A helpful result for proving inherent ambiguity. Mathematical Systems Theory. 2 (3): 191–194.
-*[http://archive.numdam.org/ARCHIVE/ITA/ITA_1978__12_3/ITA_1978__12_3_201_0/ITA_1978__12_3_201_0.pdf On languages satisfying Ogden's lemma]
+* [http://archive.numdam.org/ARCHIVE/ITA/ITA_1978__12_3/ITA_1978__12_3_201_0/ITA_1978__12_3_201_0.pdf On languages satisfying Ogden's lemma]
-*[http://ccf.ee.ntu.edu.tw/~yen/courses/toc14/chapter-2a.pdf Ogden's lemma]
+* [http://ccf.ee.ntu.edu.tw/~yen/courses/toc14/chapter-2a.pdf Ogden's lemma]
 [[Категория: Теория формальных языков]]
 [[Категория: Контекстно-свободные грамматики]]
 [[Категория: Опровержение контекстно-свободности языка]]

@@ Строка 43: / Строка 43: @@
   }}
-=== Пример <tex>2</tex> ===
+=== Пример <tex> 2 </tex> ===
 {{Утверждение
 |statement=Язык <tex>L = {a^mb^nc^l}</tex>,  где <tex> m, n, l </tex> {{---}} попарно различны, не является КС-языком.

@@ Строка 26: / Строка 26: @@
 == Примеры не КС-языка, для которого выполняется лемма ==
 Следует обратить особое внимание на то,  что лемма содержит лишь необходимые условия принадлежности КС языку.
-===Пример <tex>1</tex>===
+===Пример <tex> 1 </tex>===
 {{Утверждение
 |statement=Можно построить такой язык, для которого будет выполняться лемма Огдена, однако язык не будет контекстно-свободным.

← Предыдущая		Версия 17:55, 13 марта 2018
Строка 21:		Строка 21:


−	Условие (1) выполнено, поскольку <tex>x</tex> содержит выделенную вершину, а именно <tex>v_p</tex>. Очевидно, что условие (4) выполнено в силу предложенного разбиения <tex>\omega</tex>. Кроме того, <tex>u</tex> содержит выделенную вершину, а именно потомка некоторого сына вершины <tex>u_1</tex>. Аналогично, выделенный потомок некоторого сына вершины <tex>a</tex> содержится в <tex>v</tex>. Таким образом, условие (2) выполнено. Поскольку между <tex>v_p</tex> и <tex>a</tex> не более <tex>2m + 3</tex> вершин, вершина <tex>a</tex> имеет не более <tex>n</tex> выделенных потомков, поэтому условие (3) выполнено.	+	Условие <tex>(1)</tex> выполнено, поскольку <tex>x</tex> содержит выделенную вершину, а именно <tex>v_p</tex>. Очевидно, что условие <tex>(4)</tex> выполнено в силу предложенного разбиения <tex>\omega</tex>. Кроме того, <tex>u</tex> содержит выделенную вершину, а именно потомка некоторого сына вершины <tex>u_1</tex>. Аналогично, выделенный потомок некоторого сына вершины <tex>a</tex> содержится в <tex>v</tex>. Таким образом, условие <tex>(2)</tex> выполнено. Поскольку между <tex>v_p</tex> и <tex>a</tex> не более <tex>2m + 3</tex> вершин, вершина <tex>a</tex> имеет не более <tex>n</tex> выделенных потомков, поэтому условие <tex>(3)</tex> выполнено.
	}}		}}

@@ Строка 25: / Строка 25: @@
 == Примеры не КС-языка, для которого выполняется лемма ==
 ===Пример 1===
 {{Утверждение
@@ Строка 61: / Строка 62: @@
 Заметим, что возможность выделения символов существенно упрощает анализ данного языка, так как позволяет считать, что цепочка <tex>v</tex> может расположиться единственным способом. Иначе, т.е. при использовании леммы о разрастании для кс-языков, решение задачи было бы, по меньшей мере, сильно затруднено.
 }}
 == См. также ==

← Предыдущая		Версия 14:52, 19 января 2017
Строка 1:		Строка 1:
−	~~Понятно, что для~~ бесконечного языка применение приведённых в предыдущем разделе приёмов приведёт к началу построения в общем случае бесконечного числа правил грамматики~~, бесконечного (а не конечного) автомата и т.д., т.е. построения, которое никогда не закончится~~. Требуется более мощный аппарат, которым служит доказываемая ниже лемма Огдена.	+	Для бесконечного языка применение приведённых в предыдущем разделе приёмов приведёт к началу построения в общем случае бесконечного числа правил грамматики. Требуется более мощный аппарат, которым служит доказываемая ниже лемма Огдена.

	== Лемма ==		== Лемма ==