Локальные автоматы - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:11:07Z

rollbackEdits.php mass rollback

185.220.100.252 в 06:10, 1 сентября 2022

2022-09-01T06:10:31Z

Vsklamm: /* Алгоритм Глушкова */

2018-04-18T14:47:58Z

‎Алгоритм Глушкова

Vsklamm: /* Пример работы */

2018-04-18T14:47:29Z

‎Пример работы

Vsklamm: /* Пример работы */

2018-04-18T14:47:03Z

‎Пример работы

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

2018-04-05T13:19:51Z

‎Описание

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

2018-04-05T13:19:20Z

‎Описание

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

2018-04-02T16:23:45Z

‎Описание

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

2018-04-02T16:22:55Z

‎Описание

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

2018-04-02T15:55:38Z

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

← Предыдущая		Версия 16:11, 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:10, 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 Майкл Наки].
		+	\|}
		+
	==Описание==		==Описание==

@@ Строка 114: / Строка 114: @@
 Дано регулярное выражение <tex>e</tex>. Алгоритм Глушкова строит недетерминированный автомат, который распознает язык <tex>L(e)</tex>, распознаваемый <tex>e</tex>. Построение происходит в несколько шагов:
-. Линеаризация регулярного выражения. Каждый символ из алфавита, содержащийся в регулярном выражении, переименовывается таким образом, что каждый символ содержится в новом регулярном выражении не более одного раза. Пусть <tex>A</tex> {{---}} исходный алфавит, <tex>B</tex> {{---}} новый алфавит.
+* Линеаризация регулярного выражения. Каждый символ из алфавита, содержащийся в регулярном выражении, переименовывается таким образом, что каждый символ содержится в новом регулярном выражении не более одного раза. Пусть <tex>A</tex> {{---}} исходный алфавит, <tex>B</tex> {{---}} новый алфавит.
-. Вычисление множеств <tex>P(e'), S(e'), N(e')</tex>, где <tex>e'</tex> {{---}} линеаризованное регулярное выражение. <tex>P(e')</tex> {{---}} множество символов, с которых начинается слово из <tex>L(e')</tex>. <tex>S(e')</tex> {{---}} множество символов, на которые оканчивается слово из <tex>L(e')</tex> и <tex>N(e')</tex> {{---}} множество пар символов, которые встречаются в слове из <tex>L(e')</tex>. Более формально: <br><tex>P(e')=\{a\in B\mid aB^*\cap L(e')\ne\emptyset\}</tex>,<br><tex>S(e')=\{a\in B\mid B^*a\cap L(e')\ne\emptyset\}</tex>,<br><tex>N(e')=\{u\in B^2\mid B^*uB^*\cap L(e')\ne\emptyset\}</tex>.
+* Вычисление множеств <tex>P(e'), S(e'), N(e')</tex>, где <tex>e'</tex> {{---}} линеаризованное регулярное выражение. <tex>P(e')</tex> {{---}} множество символов, с которых начинается слово из <tex>L(e')</tex>. <tex>S(e')</tex> {{---}} множество символов, на которые оканчивается слово из <tex>L(e')</tex> и <tex>N(e')</tex> {{---}} множество пар символов, которые встречаются в слове из <tex>L(e')</tex>. Более формально: <br><tex>P(e')=\{a\in B\mid aB^*\cap L(e')\ne\emptyset\}</tex>,<br><tex>S(e')=\{a\in B\mid B^*a\cap L(e')\ne\emptyset\}</tex>,<br><tex>N(e')=\{u\in B^2\mid B^*uB^*\cap L(e')\ne\emptyset\}</tex>.
-. Вычисление множества <tex>\Lambda(e')</tex> такого что <tex>\Lambda(e')=\{\varepsilon\}\cap L(e')</tex>.
+* Вычисление множества <tex>\Lambda(e')</tex> такого что <tex>\Lambda(e')=\{\varepsilon\}\cap L(e')</tex>.
-. Вычисление локального языка с заданными множествами и построение по нему автомата.
+* Вычисление локального языка с заданными множествами и построение по нему автомата.
-. Делинеаризация, переименование каждого символа из <tex>B</tex> в соответствующий ему символ из <tex>A</tex>.
+* Делинеаризация, переименование каждого символа из <tex>B</tex> в соответствующий ему символ из <tex>A</tex>.
 ===Пример работы===

@@ Строка 127: / Строка 127: @@
 [[Файл:Glushkov_lin_automata.jpg|frame|right|Автомат, построенный в ходе работы алгоритма Глушкова]]
-Рассмотрим регулярное выражение <tex>e = (a(ab)^*)^* + (ba)^*</tex>.
+Рассмотрим регулярное выражение <tex>e = (a(ab)^*)^* + (ba)^*</tex>:
 * Линеаризуем его путем добавления индекса к каждому символу:

@@ Строка 129: / Строка 129: @@
 Рассмотрим регулярное выражение <tex>e = (a(ab)^*)^* + (ba)^*</tex>.
-. Линеаризуем его путем добавления индекса к каждому символу:
+* Линеаризуем его путем добавления индекса к каждому символу:
 :<tex>e'=(a_1(a_2b_3)^*)^*+(b_4a_5)^*</tex>.
-. Составим множества <tex>P</tex>, <tex>S</tex>, и <tex>N</tex>:
+* Составим множества <tex>P</tex>, <tex>S</tex>, и <tex>N</tex>:
 :<tex>P(e')=\{a_1,b_4\}</tex>,<br />
 :<tex>S(e')=\{a_1,b_3,a_5\}</tex>,<br />
@@ Строка 139: / Строка 139: @@
 Так как пустое слово принадлежит языку, то <math>\Lambda(e')=\{\varepsilon\}</math>.
-. Автомат локального языка <tex>L'=P'B^*\cap B^*S'\setminus B^*(B^2\setminus N')B^*</tex> содержит начальное состояние, обозначенное как <tex>1</tex>, и состояния для каждого из пяти символов алфавита <tex>B=\{a_1, a_2, b_3, b_4, a_5\}</tex>.<br>
+* Автомат локального языка <tex>L'=P'B^*\cap B^*S'\setminus B^*(B^2\setminus N')B^*</tex> содержит начальное состояние, обозначенное как <tex>1</tex>, и состояния для каждого из пяти символов алфавита <tex>B=\{a_1, a_2, b_3, b_4, a_5\}</tex>.<br>
 В построенном автомате существует переход из <tex>1</tex> (соответствующего пустой строке) в два состояния из <tex>P'</tex>, переход из <tex>a</tex> в <tex>b</tex> если <tex>ab \in N'</tex>, три состояния <math>S'</math> терминальные (как и состояние <tex>1</tex>).
-. Получим автомат для <tex>L(e)</tex>, удалив индексы, добавленные на первом этапе.
+* Получим автомат для <tex>L(e)</tex>, удалив индексы, добавленные на первом этапе.
 == См. также ==

@@ Строка 113: / Строка 113: @@
 ===Описание===
 Дано регулярное выражение <tex>e</tex>. Алгоритм Глушкова строит недетерминированный автомат, который распознает язык <tex>L(e)</tex>, распознаваемый <tex>e</tex>. Построение происходит в несколько шагов:
-# Линеаризация регулярного выражения. Каждый символ из алфавита, содержащийся в регулярном выражении, переименовывается таким образом, что каждый символ содержится в новом регулярном выражении не более одного раза. Пусть <tex>A</tex> {{---}} исходный алфавит, <tex>B</tex> {{---}} новый алфавит.
+. Линеаризация регулярного выражения. Каждый символ из алфавита, содержащийся в регулярном выражении, переименовывается таким образом, что каждый символ содержится в новом регулярном выражении не более одного раза. Пусть <tex>A</tex> {{---}} исходный алфавит, <tex>B</tex> {{---}} новый алфавит.
-# Вычисление множеств <tex>P(e'), S(e'), N(e')</tex>, где <tex>e'</tex> {{---}} линеаризованное регулярное выражение. <tex>P(e')</tex> {{---}} множество символов, с которых начинается слово из <tex>L(e')</tex>. <tex>S(e')</tex> {{---}} множество символов, на которые оканчивается слово из <tex>L(e')</tex> и <tex>N(e')</tex> {{---}} множество пар символов, которые встречаются в слове из <tex>L(e')</tex>. Более формально: <br><tex>P(e')=\{a\in B\mid aB^*\cap L(e')\ne\emptyset\}</tex>,<br><tex>S(e')=\{a\in B\mid B^*a\cap L(e')\ne\emptyset\}</tex>,<br><tex>N(e')=\{u\in B^2\mid B^*uB^*\cap L(e')\ne\emptyset\}</tex>.
-# Вычисление множества <tex>\Lambda(e')</tex> такого что <tex>\Lambda(e')=\{\varepsilon\}\cap L(e')</tex>.
+. Вычисление множеств <tex>P(e'), S(e'), N(e')</tex>, где <tex>e'</tex> {{---}} линеаризованное регулярное выражение. <tex>P(e')</tex> {{---}} множество символов, с которых начинается слово из <tex>L(e')</tex>. <tex>S(e')</tex> {{---}} множество символов, на которые оканчивается слово из <tex>L(e')</tex> и <tex>N(e')</tex> {{---}} множество пар символов, которые встречаются в слове из <tex>L(e')</tex>. Более формально: <br><tex>P(e')=\{a\in B\mid aB^*\cap L(e')\ne\emptyset\}</tex>,<br><tex>S(e')=\{a\in B\mid B^*a\cap L(e')\ne\emptyset\}</tex>,<br><tex>N(e')=\{u\in B^2\mid B^*uB^*\cap L(e')\ne\emptyset\}</tex>.
-# Вычисление локального языка с заданными множествами и построение по нему автомата.
-# Делинеаризация, переименование каждого символа из <tex>B</tex> в соответствующий ему символ из <tex>A</tex>.
+. Вычисление множества <tex>\Lambda(e')</tex> такого что <tex>\Lambda(e')=\{\varepsilon\}\cap L(e')</tex>.
 ===Пример работы===
 [[Файл:Glushkov_lin_automata.jpg|frame|right|Автомат, построенный в ходе работы алгоритма Глушкова]]

@@ Строка 41: / Строка 41: @@
 :Пусть <tex>G</tex> {{---}} граф Майхилла.
 :Построим автомат <tex>\mathcal{A}</tex> следующим образом:
-:* Добавим вершину <tex>c_i</tex> в <tex>G</tex> с ребрами от <tex>c_i</tex> к каждой стартовой вершине <tex>G</tex>; отметим вершину <tex>c_i</tex> как стартовое состояние.
+:* Добавим вершину <tex>i</tex> в <tex>G</tex> с ребрами от <tex>i</tex> к каждой стартовой вершине <tex>G</tex>; отметим вершину <tex>i</tex> как стартовое состояние.
 :* Отметим конечные вершины как терминальные состояния.
 :* Отметим каждое ребро результирующего ориентированного графа символом, стоящим в вершине, на которою оно указывает.

@@ Строка 41: / Строка 41: @@
 :Пусть <tex>G</tex> {{---}} граф Майхилла.
 :Построим автомат <tex>\mathcal{A}</tex> следующим образом:
-:* Добавим вершину <tex>\Diamond</tex> в <tex>G</tex> с ребрами от <tex>\Diamond</tex> к каждой стартовой вершине <tex>G</tex>; отметим вершину <tex>\Diamond</tex> как стартовое состояние.
+:* Добавим вершину <tex>c_i</tex> в <tex>G</tex> с ребрами от <tex>c_i</tex> к каждой стартовой вершине <tex>G</tex>; отметим вершину <tex>c_i</tex> как стартовое состояние.
 :* Отметим конечные вершины как терминальные состояния.
 :* Отметим каждое ребро результирующего ориентированного графа символом, стоящим в вершине, на которою оно указывает.
@@ Строка 50: / Строка 50: @@
 :Покажем, что полученный автомат конечен.
 :Ребра, выходящие из стартового состояния обозначены различными символами, потому что они указывают на вершины, которые, по свойству 3, были отмечены различными символами в исходном автомате.
-:Если мы рассмотрим любое другое состояние <tex>s</tex>, то два перехода из <tex>s</tex> могут иметь одинаковые метки только в том случае, если в <tex>G</tex> оба ориентированных ребра идут в одну и ту же вершину. Но этого не может быть по свойтсву 1.
+:Если мы рассмотрим любое другое состояние <tex> s </tex>, то два перехода из <tex> s </tex> могут иметь одинаковые метки только в том случае, если в <tex>G</tex> оба ориентированных ребра идут в одну и ту же вершину. Но этого не может быть по свойству 1.
 :То есть <tex>\mathcal{A}</tex> {{---}} [[Детерминированные_конечные_автоматы | ДКА]]. По построению он является стандартным локальным автоматом.
-:Теперь просто проверить, что <tex>L(\mathcal{A}) = L(G)</tex>.
+:Теперь просто проверить, что <tex>L(\mathcal{A}) = L(G) </tex>.
-<tex>\Leftarrow</tex>
+<tex> \Leftarrow </tex>
-:Пусть <tex>\mathcal{A} = (S, \Sigma, i, \delta, T)</tex> {{---}} стандартный локальный автомат, стартовое состояние которого не является терминальным.
+:Пусть <tex> \mathcal{A} = (S, \Sigma, i, \delta, T) </tex> {{---}} стандартный локальный автомат, стартовое состояние которого не является терминальным.
 :Построим по нему граф Майхилла следующим образом:
-:* Отметим все состояния <tex>\mathcal{A}</tex>, кроме стартового, <tex>input</tex> символами, стоящими на ребрах, входящих в эти состояния.
+:* Отметим все состояния <tex> \mathcal{A} </tex>, кроме стартового, <tex> input </tex> символами, стоящими на ребрах, входящих в эти состояния.
-:* Сотрем все метки на ребрах <tex>\mathcal{A}</tex>.
+:* Сотрем все метки на ребрах <tex> \mathcal{A} </tex>.
-:* Отметим все состояния <tex>s</tex> как начальные вершины, если существует переход из <tex>i</tex> в <tex>s</tex>
+:* Отметим все состояния <tex> s </tex> как начальные вершины, если существует переход из <tex> i </tex> в <tex> s </tex>
 :* Отметим все терминальные состояния как конечные вершины.
-:* Удалим вершину <tex>i</tex> и все ребра, исходящие из нее.
+:* Удалим вершину <tex> i </tex> и все ребра, исходящие из нее.
-:Назовем полученный граф <tex>G</tex> {{---}} он будет графом Майхилла по построению. Легко проверить, что <tex>L(G) = L(\mathcal{A})</tex>.
+:Назовем полученный граф <tex> G </tex> {{---}} он будет графом Майхилла по построению. Легко проверить, что <tex> L(G) = L(\mathcal{A}) </tex>.
 }}

@@ Строка 142: / Строка 142: @@
 == Источники информации ==
-* Хопкрофт Д., Мотвани Р., Ульман Д. {{---}} Введение в теорию автоматов, языков и вычислений
+* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' {{---}} Введение в теорию автоматов, языков и вычислений
-* Mark V. Lawson {{---}} Finite Automata
+* ''Mark V. Lawson'' {{---}} Finite Automata
 * [https://en.wikipedia.org/wiki/Glushkov's_construction_algorithm Wikipedia {{---}} Glushkov's construction algorithm]