Эквивалентность ДМП-автоматов - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:44:10Z

rollbackEdits.php mass rollback

185.220.100.241 в 03:19, 1 сентября 2022

2022-09-01T03:19:05Z

Oxygen31 в 22:20, 16 января 2017

2017-01-16T22:20:14Z

Внесённые изменения

Shersh: переименовал Эквивалентность ДМП автоматов в Эквивалентность ДМП-автоматов: люблю дефисы

2017-01-16T21:09:04Z

переименовал Эквивалентность ДМП автоматов в Эквивалентность ДМП-автоматов: люблю дефисы

Oxygen31 в 21:03, 16 января 2017

2017-01-16T21:03:47Z

Oxygen31 в 21:02, 16 января 2017

2017-01-16T21:02:09Z

94.25.229.232: Новая страница: «Предположим детерминированный строгий автомат с единственным состоянием с элементами, ...»

2017-01-16T01:21:35Z

Новая страница: «Предположим детерминированный строгий автомат с единственным состоянием с элементами, ...»

Новая страница

Предположим детерминированный строгий автомат с единственным состоянием с элементами, представленный тройкой: входной алфавит на ленте <tex>\Sigma</tex>, стековым алфавит <tex>\Gamma</tex> и множеством переходов <tex>\Delta</tex>. Мы предполагаем наличие полного порядка на <tex>\Sigma</tex>,и говорим, что слово <tex>u</tex> короче слова <tex>v</tex> если <tex>|u| < |v|</tex> или <tex>|u| = |v|</tex> и <tex>u</tex> лексикографически меньше <tex>v</tex>. Пусть <tex>E, F, G,\dotsc</tex> - допустимые конфигурации.
{{Определение
|definition=<tex>E \cdot u</tex> - '''конфигурация <tex>E</tex> после слова <tex>u</tex>''', единственная допустимая конфигурация <tex>F</tex> такая что <tex>(E, u) \rightarrow F</tex>, которая может быть и <tex>\emptyset</tex>.
}}
{{Определение
|definition=Язык, задаваемой конфигурацией <tex>E</tex>, <tex>L(E) = \{ E : (E \cdot u) = \varepsilon \}</tex>.
}}
{{Определение
|definition=<tex>E \sim F</tex> - две конфигурации <tex>E</tex> и <tex>F</tex> '''эквивалентны''' если <tex>L(E) = L(F)</tex>.
}}

Равенство задаваемых языков также может быть приблизительным.
{{Определение
|definition=<tex>E \sim_n F, n \geq 0</tex> - конфигурафии <tex>E</tex> и <tex>F</tex> '''<tex>n</tex>-эквивалентны''' если они принимают одни и те же слова, длина которых не больше <tex>n</tex>:
<br>для всех слов <tex>w</tex>, таких что <tex>|w| \leq n, (E \cdot w) = \varepsilon</tex> тогда и только тогда, когда <tex>(F \cdot w) = \varepsilon</tex>
}}

{{Утверждение
|statement=
Справедливы следующие факты:
# <tex>E \sim F</tex> тогда и только тогда, когда для любого <tex> n \geq 0</tex> выполняется <tex>E \sim_n F</tex>
# Если <tex>E \nsim F</tex>, то существует <tex> n \geq 0</tex> такой, что <tex>E \sim_n F</tex> и <tex>E \nsim_{n+1} F</tex>
# Если <tex>E \sim F</tex>, то для любого <tex>u \in \Sigma^*</tex>, <tex>(E \cdot u) \sim (F \cdot u)</tex>.
# <tex>E \sim_{n} F</tex>, тогда и только тогда, когда для любого <tex>u \in \Sigma^*</tex>, где <tex>|u| \leq n</tex>, <tex>(E \cdot u) \sim_{n-|u|} (F \cdot u)</tex>.
# Если <tex>E \sim_{n} F</tex> и <tex>0 \leq m < n</tex>, то <tex>E \sim_{m} F</tex>.
# Если <tex>E \sim_{n} F</tex> и <tex>F \nsim_{n} G</tex>, то <tex>E \nsim_{n} G</tex>.
}}

{{Определение
|definition=Для каждого стекового символа <tex>X</tex> словом <tex>w(X)</tex> называется самое короткое слово в множестве <tex>\{u : (X \cdot u) = \varepsilon \}</tex>
}}

{{Определение
|definition=<tex>E = E_1G_1 + ... + E_nG_n</tex> находится в форме голова/хвост, если голова <tex>E_1 + ...+E_n</tex> допустима и хотя бы один <tex>E_i= \emptyset</tex>, и каждый хвост <tex>G_i = \emptyset</tex>.
}}

Приведём некоторые свойства формы голова/хвост. Эквивалентность и n-эквивалентность языков согласуются с операциями <tex>+</tex> и суммы. Следовательно, форма голова/хвост позволяет подставить эквивалентное выражение в хвост (т.к. допустимость сохраняется).

{{Утверждение
|statement=
Пусть <tex>E = E_1G_1 + ... + E_nG_n</tex>, тогда справедливы следующие факты:
# Если <tex>(E_i \cdot u) = \varepsilon</tex>, то для всех <tex>j \neq i</tex> выполняется <tex>(E_j \cdot u) = \emptyset</tex> и <tex>(E \cdot u) = G_i</tex>
# Если <tex>(E_i \cdot u) = \emptyset</tex>, то <tex>(E \cdot u) = (E_1 \cdot u)G_1 + ... + (E_n \cdot u)G_n</tex>.
# Если <tex>H_i \neq \emptyset, 1 \leq i \leq n</tex>, то <tex>E_1H_1 + ... + E_nH_n</tex> в форме голова/хвост.
# Если каждая <tex>H_i \neq \emptyset</tex> и каждая <tex>E_i \neq \varepsilon</tex> и для каждого <tex>j</tex> такого, что <tex>E_j \neq \emptyset</tex> выполняется <tex>H_j \sim_m G_j</tex>, то <tex>E \sim{m+1} E_1H_1 + ... + E_nH_n</tex>.
# Если <tex>H_i \sim G_i, 1 \leq i \leq n</tex>, то <tex>E \sim E_1H_1 + ... + E_nH_n</tex>.
}}

Две конфигурации могут иметь одинаковые головы и разные хвосты, или одинаковые хвосты и различие в головах. Если <tex>E</tex> представлена в форме голова/хвост<tex>E_1G_1 + ... + E_nG_n</tex> и <tex>F</tex> имеет схожую форму голова/хвост <tex>F_1G_1 + ... + E_nF_n</tex>, имеющая тот же самый хвост. Несоответствие между <tex>E</tex> и <tex>F</tex>, соответственное этому представлению - это <tex>max\{|E_i|, |F_i| : 1 \leq i \leq n\}</tex>. Если несоответствие равно 0, то конфигурации одинаковы.

'''Замечание:''' любая пара конфигураций <tex>E</tex> и <tex>F</tex> имеет форму голова/хвост включающую в себя одинаковые хвосты: <tex> E = EG</tex> и <tex>F = FG</tex>, где <tex>G = \varepsilon</tex>.

{{Определение
|definition= Если <tex>E = E_1G_1 + ... + E_nG_n</tex> и <tex>F = F_1F_1 + ... + F_nF_n</tex>, тогда <tex>F</tex> в его форме голова/хвост - '''хвостовое дополнение <tex>E</tex>''' в его форме голова/хвост обеспечивается <tex>H_i = K^i_1G_1 + ... + K^i_nG_n, 1 \leq i \leq m</tex>. Когда <tex>F</tex> - хвостовое дополнение <tex>E</tex>, относящиеся к нему дополнение <tex>e</tex> - кортеж из m элементов <tex>(K^1_1+...+K_n^1,...,K_1^m +...+K_n^m)</tex> без <tex>G_is</tex>, и говорится, что <tex>F</tex> дополняет <tex>E</tex> с помощью <tex>e</tex>.
}}

Можно рассматривать дополнения как матрицы. Если <tex>E''</tex> расширяет <tex>E'</tex> с помощью <tex>e</tex> и <tex>E'</tex> расширяет <tex>E</tex> с помощью <tex>f</tex>, то <tex>E''</tex> расширяет <tex>E</tex> с помощью <tex>ef</tex>(в смысле умножения матриц).

Особый случай расширения возникает когда хвосты одинаковы. Если <tex>E = E_1G_1 + ... + E_nG_n</tex> и <tex>F = F_1G_1+...+F_nG_n</tex>, тогда <tex>F</tex> расширяет <tex>E</tex> с помощью <tex>e = ( \varepsilon + \emptyset +... + \emptyset ,..., \emptyset + \emptyset +...+ \varepsilon)</tex>. Расширение <tex>e</tex> сокращается до тождества <tex>\varepsilon</tex> (аналог единичной матрицы).

← Предыдущая		Версия 16:44, 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 Майкл Наки].
−	\|}
−
	[[Нормальная форма ДМП-автомата\|Предположим детерминированный строгий автомат с единственным состоянием с элементами, представленный тройкой]]:		[[Нормальная форма ДМП-автомата\|Предположим детерминированный строгий автомат с единственным состоянием с элементами, представленный тройкой]]:
	* входной алфавит на ленте <tex>\Sigma</tex>,		* входной алфавит на ленте <tex>\Sigma</tex>,

← Предыдущая		Версия 03:19, 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 Майкл Наки].
		+	\|}
		+
	[[Нормальная форма ДМП-автомата\|Предположим детерминированный строгий автомат с единственным состоянием с элементами, представленный тройкой]]:		[[Нормальная форма ДМП-автомата\|Предположим детерминированный строгий автомат с единственным состоянием с элементами, представленный тройкой]]:
	* входной алфавит на ленте <tex>\Sigma</tex>,		* входной алфавит на ленте <tex>\Sigma</tex>,

@@ Строка 1: / Строка 1: @@
-Предположим детерминированный строгий автомат с единственным состоянием с элементами, представленный тройкой: входной алфавит на ленте <tex>\Sigma</tex>, стековым алфавит <tex>\Gamma</tex> и множеством переходов <tex>\Delta</tex>. Мы предполагаем наличие полного порядка на <tex>\Sigma</tex>,и говорим, что слово <tex>u</tex> короче слова <tex>v</tex> если <tex>|u| < |v|</tex> или <tex>|u| = |v|</tex> и <tex>u</tex> лексикографически меньше <tex>v</tex>. Пусть <tex>E, F, G,\dotsc</tex> - допустимые конфигурации.
+[[Нормальная форма ДМП-автомата|Предположим детерминированный строгий автомат с единственным состоянием с элементами, представленный тройкой]]: входной алфавит на ленте <tex>\Sigma</tex>, стековым алфавит <tex>\Gamma</tex> и множеством переходов <tex>\Delta</tex>. Мы предполагаем наличие полного порядка на <tex>\Sigma</tex>,и говорим, что слово <tex>u</tex> короче слова <tex>v</tex> если <tex>|u| < |v|</tex> или <tex>|u| = |v|</tex> и <tex>u</tex> лексикографически меньше <tex>v</tex>. Пусть <tex>E, F, G,\dotsc</tex> - допустимые конфигурации.
 {{Определение
 |definition=<tex>E \cdot u</tex> - конфигурация '''<tex>E</tex> после слова <tex>u</tex>''', единственная допустимая конфигурация <tex>F</tex> такая что <tex>(E, u) \rightarrow F</tex>, которая может быть и <tex>\emptyset</tex>.

← Предыдущая	Версия 21:09, 16 января 2017
(нет различий)

@@ Строка 1: / Строка 1: @@
 Предположим детерминированный строгий автомат с единственным состоянием с элементами, представленный тройкой: входной алфавит на ленте <tex>\Sigma</tex>, стековым алфавит <tex>\Gamma</tex> и множеством переходов <tex>\Delta</tex>. Мы предполагаем наличие полного порядка на <tex>\Sigma</tex>,и говорим, что слово <tex>u</tex> короче слова <tex>v</tex> если <tex>|u| < |v|</tex> или <tex>|u| = |v|</tex> и <tex>u</tex> лексикографически меньше <tex>v</tex>. Пусть <tex>E, F, G,\dotsc</tex> - допустимые конфигурации.
 {{Определение
-|definition=<tex>E \cdot u</tex> - '''конфигурация <tex>E</tex> после слова <tex>u</tex>''', единственная допустимая конфигурация <tex>F</tex> такая что <tex>(E, u) \rightarrow F</tex>, которая может быть и <tex>\emptyset</tex>.
+|definition=<tex>E \cdot u</tex> - конфигурация '''<tex>E</tex> после слова <tex>u</tex>''', единственная допустимая конфигурация <tex>F</tex> такая что <tex>(E, u) \rightarrow F</tex>, которая может быть и <tex>\emptyset</tex>.
 }}
 {{Определение
@@ Строка 12: / Строка 12: @@
 Равенство задаваемых языков также может быть приблизительным.
 {{Определение
 |definition=<tex>E \sim_n F,  n \geq 0</tex> - конфигурафии <tex>E</tex> и <tex>F</tex> '''<tex>n</tex>-эквивалентны'''  если они принимают одни и те же слова, длина которых не больше <tex>n</tex>:
 <br>для всех слов <tex>w</tex>, таких что <tex>|w| \leq n, (E \cdot w) = \varepsilon</tex> тогда и только тогда, когда <tex>(F \cdot w) = \varepsilon</tex>
 }}
@@ Строка 55: / Строка 55: @@
 }}
 Можно рассматривать дополнения как матрицы. Если <tex>E''</tex> расширяет <tex>E'</tex> с помощью <tex>e</tex> и <tex>E'</tex> расширяет <tex>E</tex> с помощью <tex>f</tex>, то <tex>E''</tex> расширяет <tex>E</tex> с помощью <tex>ef</tex>(в смысле умножения матриц).
 Особый случай расширения возникает когда хвосты одинаковы. Если <tex>E = E_1G_1 + ... + E_nG_n</tex> и <tex>F = F_1G_1+...+F_nG_n</tex>, тогда <tex>F</tex> расширяет <tex>E</tex> с помощью <tex>e = ( \varepsilon + \emptyset +... + \emptyset ,..., \emptyset + \emptyset +...+ \varepsilon)</tex>. Расширение <tex>e</tex> сокращается до тождества <tex>\varepsilon</tex> (аналог единичной матрицы).