| НЕТ ВОЙНЕ
|
|
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
Антивоенный комитет России
|
| Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
|
| meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.
|
Автоматы с [math]\varepsilon[/math]-переходами
Конечный автомат с [math]\varepsilon[/math]-переходами — конечный автомат, в котором есть возможность совершать переходы по [math]\varepsilon[/math].
| Определение: |
| [math]\varepsilon[/math]-НКА или НКА с [math]\varepsilon[/math]-переходами (англ. [math]\varepsilon[/math]-moves) — набор [math]A={\langle\Sigma,Q,s,T,\delta\rangle}[/math], где все компоненты имеют тот же смысл, что и для НКА, за исключением [math]\delta : Q\times (\Sigma\cup\{\varepsilon\}) \to 2^Q[/math]. |
Эквивалентность автоматов с переходами по строкам и НКА. [math]\varepsilon[/math]-замыкание
Будем называть два автомата эквивалентными, если они задают один и тот же язык.
Рассмотрим автомат, в котором переходы осуществляются по строкам. Это переходы вида [math]\langle p,\alpha\beta\rangle\vdash\langle q,\beta\rangle[/math], где [math]\alpha,\beta[/math] — строки.
| Теорема: |
|
| Доказательство: |
| [math]\triangleright[/math] |
|
Рассмотрим два случая:
- [math]\left | \alpha \right | \geqslant 1[/math]
- Заменим переходы по таким строкам на последовательности переходов по символам. А именно, пусть [math]\alpha=a_1a_2 \ldots a_n[/math], где [math]a_1,a_2, \ldots ,a_n[/math] — символы. Заменим переход [math]\langle p,\alpha\beta\rangle\vdash\langle q,\beta\rangle[/math] на переходы [math]{\langle p,\alpha\beta\rangle\vdash\langle t_1, a_1^{-1}\alpha\beta\rangle},{\langle t_1,a_1^{-1}\alpha\beta\rangle\vdash\langle t_2,(a_1a_2)^{-1}\alpha\beta\rangle}, \ldots ,{\langle t_{n-1}, a_n\beta\rangle\vdash\langle q, \beta\rangle}.[/math]
- [math]\left | \alpha \right | = 0 \Rightarrow \alpha = \varepsilon[/math]
- Рассматриваем автомат [math]A[/math] с [math]\varepsilon[/math]-переходами. Для доказательства его эквивалентности НКА построим его [math]\varepsilon[/math]-замыкание.
| Определение: |
| [math]\varepsilon[/math]-замыкание (англ. [math]\varepsilon[/math]-closure) — построение по автомату с [math]\varepsilon[/math]-переходами эквивалентного ему автомата без [math]\varepsilon[/math]-переходов. |
Ход построения [math]\varepsilon[/math]-замыкания:
- Транзитивное замыкание
- Пусть [math]B[/math] — подграф [math]A[/math], в котором есть только [math]\varepsilon[/math]-переходы. Сделаем транзитивное замыкание графа [math]B[/math]. Таким образом, получим из автомата [math]A[/math] новый автомат [math]A_1[/math], который допускает тот же язык. Заметим, что если [math]A_1[/math] допускает слово [math]x[/math], то он допускает [math]x[/math], не совершая двух [math]\varepsilon[/math]-переходов подряд.
- Добавление допускающих состояний
- Пусть в [math]A_1[/math] есть [math]\varepsilon[/math]-переход из состояния [math]u[/math] в состояние [math]v[/math], причем [math]v[/math] — допускающее. Тогда, если текущее состояние [math]u[/math] и строка закончилась, то её можно допустить. Во всех таких случаях сделаем [math]u[/math] допускающим. Получим автомат [math]A_2[/math], обладающий тем же свойством, что и [math]A_1[/math], а также не совершающий [math]\varepsilon[/math]-переходов в качестве последнего перехода.
- Добавление рёбер
- Во всех случаях, когда [math]{\delta(u,\varepsilon)=v}, {\delta(v,c)=w}[/math], добавим переход [math]\delta(u,c)=w[/math]. Заметим, что если полученный автомат [math]A_3[/math] допускает [math]x[/math], то он допускает [math]x[/math], не совершая [math]\varepsilon[/math]-переходов.
- Устранение [math]\varepsilon[/math]-переходов
- Из предыдущего замечания следует, что если теперь устранить [math]\varepsilon[/math]-переходы, то допускаемый язык не изменится. Уберем из [math]A_3[/math] все [math]\varepsilon[/math]-переходы.
Получили НКА без [math]\varepsilon[/math]-переходов, эквивалентный исходному автомату. |
| [math]\triangleleft[/math] |
Совпадение множеств языков, допускаемых [math]\varepsilon[/math]-НКА и ДКА
| Утверждение: |
|
| [math]\triangleright[/math] |
|
[math] \mathcal{L}([/math]ДКА[math]) = \mathcal{L}([/math]НКА[math])[/math]. По только что доказанной теореме, [math] \mathcal{L}([/math]НКА[math]) = \mathcal{L}([/math][math]\varepsilon[/math]-НКА[math])[/math]. Значит, [math] \mathcal{L}([/math]ДКА[math]) = \mathcal{L}([/math][math]\varepsilon[/math]-НКА[math])[/math]. |
| [math]\triangleleft[/math] |
Применение
В некоторых случаях НКА с [math]\varepsilon[/math]-переходами строятся проще, чем просто НКА и тем более ДКА для тех же языков. Доказанная выше эквивалентность [math] \mathcal{L}([/math]ДКА[math])[/math],[math]\mathcal{L}([/math]НКА[math])[/math] и [math]\mathcal{L}([/math][math]\varepsilon[/math]-НКА[math])[/math] позволяет нам при помощи алгоритма [math]\varepsilon[/math]-замыкания легко приводить одно к другому и далее к третьему. Также свойства, доказанные выше, являются важной составляющей доказательства теоремы Клини.
См. также
Источники информации
