200
правок
Изменения
→Алгоритм Глушкова
{{Определение
|definition=
'''Граф Майхилла <tex>G </tex> (над алфавитом А<tex>\Sigma</tex>)''' (англ. ''Myhill graph'') {{---}} [[Основные определения теории графов | ориентированный граф]], удовлетворяющий свойствам:1. # Для каждой упорядоченной пары вершин v1 <tex>v</tex> и v2 <tex>u</tex> существует только одно ребро из v1 <tex>v</tex> в v2<tex>u</tex>. 2. # Некоторые вершины обозначены начальными, а некоторые {{- --}} конечными. Ребро может одновременно быть начальным и конечным. 3. # Вершины обозначены различными символами из конечного алфавита А<tex>\Sigma</tex>, то есть мы можем обращаться к вершине по ее символу.
}}
Пусть <tex>G </tex> {{---}} граф Майхилла над алфавитом А<tex>\Sigma</tex>.
Символ а из А <tex>c \in \Sigma</tex> назовем разрешенным, если им помечена вершина, являющая одновременно начальной и конечной.
Не пустая строка a_1a_2...a_n <tex>c_1c_2 \ldots c_n</tex> из A<tex>\Sigma^* </tex> длиной не менее двух символов, называется разрешенной, если символом a_1 <tex>c_1</tex> отмечена стартовая вершина, а символом a_n <tex>c_n</tex> {{- --}} конечная, и для всех <tex>1 <= \leqslant i <= \leqslant n-1 </tex> в <tex>G </tex> существует ребро a_i -<tex> a_(c_i, c_{i+1})</tex>.
Язык <tex>L(G)</tex>, распознаваемый графом Майхилла, состоит из всех разрешенных строк из A <tex>\Sigma^+</tex>.
Покажем, что графы Майхилла могут быть представлены в виде автоматов. Пусть M <tex>\mathcal{A} = (S, A \Sigma, i, \delta, T) </tex> {{---}} [[Детерминированные_конечные_автоматы | ДКА, не обязательно законченный]].
{{Определение
|definition= Автомат M <tex>\mathcal{A}</tex> называется '''локальным''' (англ. ''local automaton'', 'local automation'Glushkov automaton''), если для любого a <tex>c</tex> из A <tex>\Sigma</tex> множество <tex>\{\delta(s * a: , c) \mid s \in S\} </tex> содержит не более одного элемента.
}}
{{Определение
|definition= Автомат M Локальный автомат <tex>\mathcal{A}</tex> называется '''стандартным локальным''' автоматом (англ. '''standard loal local automation'''), если в нем нет перехода в начальное состояние.
}}
Таким образом, автомат является локальным, если для каждого а <tex>c</tex> из А <tex>\Sigma</tex> нет переходов, отмеченных а<tex>c</tex>, или если все они ведут в одно состояние.
Покажем, что граф Майхилла может быть преобразован в стандартный локальный автомат таким образом, что распознаваемый им язык не изменится.
Язык распознается графом Майхилла тогда и только тогда, когда он распознается стандартным локальным автоматом, стартовое состояние которого не является терминальным.
|proof=
}}
{{Утверждение
|statement=Язык, распознаваемый локальным автоматом, является локальным.
}}
==Алгоритм Глушкова==
===Описание===
Дано регулярное выражение <tex>e</tex>. Алгоритм Глушкова строит недетерминированный автомат, который распознает язык <tex>L(e)</tex>, распознаваемый <tex>e</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>B</tex> в соответствующий ему символ из <tex>A</tex>.
===Пример работы===
[[Файл:Glushkov_lin_automata.jpg|frame|right|Автомат, построенный в ходе работы алгоритма Глушкова]]
Рассмотрим регулярное выражение <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(e')=\{a_1,b_4\}</tex>,<br />
:<tex>S(e')=\{a_1,b_3,a_5\}</tex>,<br />
:<tex>N(e')=\{a_1a_2, a_1a_1, a_2b_3, b_3a_1,b_3a_2,b_4a_5,a_5b_4\}</tex>.
Так как пустое слово принадлежит языку, то <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>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>, удалив индексы, добавленные на первом этапе.
== См. также ==
* [[Контексты и синтаксические моноиды]]
== Источники информации ==
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' {{---}} Введение в теорию автоматов, языков и вычислений
* ''Mark V. Lawson'' {{---}} Finite Automata
* [https://en.wikipedia.org/wiki/Glushkov's_construction_algorithm Wikipedia {{---}} Glushkov's construction algorithm]
[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]
[[Категория: Другие автоматы]]