Алгоритм Бржозовского - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:29:32Z

rollbackEdits.php mass rollback

80.82.78.13 в 04:38, 1 сентября 2022

2022-09-01T04:38:38Z

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

2016-11-13T13:35:23Z

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

Kiryukhinv в 17:54, 12 ноября 2016

2016-11-12T17:54:08Z

Kiryukhinv: /* Описание */

2016-11-12T17:38:11Z

‎Описание

Kiryukhinv в 17:06, 12 ноября 2016

2016-11-12T17:06:17Z

Kiryukhinv: /* Описание */

2016-11-12T16:59:48Z

‎Описание

Kiryukhinv: /* Описание */

2016-11-05T22:46:09Z

‎Описание

188.227.78.59 в 14:06, 4 ноября 2016

2016-11-04T14:06:09Z

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

2016-10-29T16:34:53Z

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

← Предыдущая		Версия 16:29, 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 =		\|definition =

← Предыдущая		Версия 04:38, 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 =		\|definition =

← Предыдущая		Версия 13:35, 13 ноября 2016
Строка 130:		Строка 130:
	[[Категория: Теория формальных языков]]		[[Категория: Теория формальных языков]]
	[[Категория: Автоматы и регулярные языки]]		[[Категория: Автоматы и регулярные языки]]
		+	[[Категория: Минимизация ДКА]]

@@ Строка 79: / Строка 79: @@
 |about=5
 |statement=
-Детерминированный полный достижимый автомат минимален тогда и только тогда, когда правые языки его состояний различны.
+Детерминированный автомат минимален тогда и только тогда, когда правые языки его состояний различны и все состояния достижимы.
 }}

@@ Строка 22: / Строка 22: @@
 |statement=
 Автомат является детерминированным тогда и только тогда, когда левые языки его состояний попарно не пересекаются.
 }}

@@ Строка 26: / Строка 26: @@
 {{Определение
 |definition=
-'''Обратное слово''' <tex>r(u)</tex> для слова <tex>u</tex> определяется следующим образом: <tex>r(\varepsilon) = \varepsilon</tex> и если <tex>u = u_1 u_2 u_3 \dotsc u_p</tex>, тогда <tex>r(u) = v_1 v_2 v_3 \dotsc v_p</tex>, где <tex>v_i = u_{p - i + 1}</tex>.
+'''Обратное слово''' (англ. ''reverse of the word'') <tex>r(u)</tex> для слова <tex>u</tex> определяется следующим образом: <tex>r(\varepsilon) = \varepsilon</tex> и если <tex>u = u_1 u_2 u_3 \dotsc u_p</tex>, тогда <tex>r(u) = v_1 v_2 v_3 \dotsc v_p</tex>, где <tex>v_i = u_{p - i + 1}</tex>.
 }}
 {{Определение
 |definition=
-'''Обратный язык''' для языка <tex>L</tex> {{---}} язык <tex>r(L) = \{ u \mid r(u) \in L \}</tex>.
+'''Обратный язык''' (англ. ''reverse of the language'') для языка <tex>L</tex> {{---}} язык <tex>r(L) = \{ u \mid r(u) \in L \}</tex>.
 }}
 {{Определение
 |definition=
-'''Обратный автомат''' для автомата <tex>\mathcal{A} = \langle \Sigma , Q , S , T , \delta \rangle</tex> {{---}} автомат <tex>r(\mathcal{A}) = \langle \Sigma , Q , T , I , r(\delta) \rangle</tex>, полученный из <tex>\mathcal{A}</tex> сменой местами начальных и конечных состояний и сменой направлений переходов.
+'''Обратный автомат''' (англ. ''reverse of the automaton'') для автомата <tex>\mathcal{A} = \langle \Sigma , Q , S , T , \delta \rangle</tex> {{---}} автомат <tex>r(\mathcal{A}) = \langle \Sigma , Q , T , I , r(\delta) \rangle</tex>, полученный из <tex>\mathcal{A}</tex> сменой местами начальных и конечных состояний и сменой направлений переходов.
 }}

@@ Строка 14: / Строка 14: @@
 '''Левым языком''' (англ. ''left language'') называется язык <tex>L_g(q)</tex>, распознаваемый автоматом <tex>\mathcal{A}</tex>, в котором <tex>q</tex> является уникальным терминальным состоянием.
   }}
 {{Утверждение

@@ Строка 85: / Строка 85: @@
 * Он работает даже с [[Недетерминированные конечные автоматы|недетерминированными конечными автоматами]].
-Пусть <tex>\mathcal{A}</tex> {{---}} конечный автомат. <tex>d(\mathcal{A})</tex> {{---}} детерминизированный автомат для <tex>\mathcal{A}</tex>, <tex>r(\mathcal{A})</tex> {{---}} обратный автомат для <tex>\mathcal{A}</tex>.<br>
+Введём следующие обозначения:
-Обозначим <tex>d(r(\mathcal{A}))</tex> как <tex>dr(\mathcal{A})</tex>, <tex>r(d(r(\mathcal{A})))</tex> как <tex>rdr(\mathcal{A})</tex>, <tex>d(r(d(r(\mathcal{A}))))</tex> как <tex>drdr(\mathcal{A})</tex>.
+*<tex>\mathcal{A}</tex> {{---}} конечный автомат,
 {{Теорема

@@ Строка 116: / Строка 116: @@
 <references/>
 ==Источники информации==
-* [http://sovietov.com/txt/minfa/minfa.html Алгоритм Бржозовского для минимизации конечного автомата]
+* [https://pdfs.semanticscholar.org/f3be/b5e5825e6eedaab7f382341c9dd9c2ab33fa.pdf J.-M. Champarnaud, A. Khorsi, T. Paranthoen {{---}} Split and join for minimizing: Brzozowski's algorithm]
 [[Категория: Теория формальных языков]]
 [[Категория: Автоматы и регулярные языки]]