188
правок
Изменения
→Алгоритм Глушкова
Дано регулярное выражение <tex>e</tex>. Алгоритм Глушкова строит недетерминированный автомат, который распознает язык <tex>L(e)</tex>, распознаваемый <tex>e</tex>. Построение происходит в несколько шагов:
# Линеаризация регулярного выражения. Каждый символ из алфавита, содержащийся в регулярном выражении, переименовывается таким образом, что каждый символ содержится в новом регулярном выражении не более одного раза. Пусть <tex>A</tex> {{---}} исходный алфавит, <tex>B</tex> {{---}} новый алфавит.
# Вычисление множеств <tex>P(e'), DS(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>.
===Пример работы===
Рассмотрим регулярное выражение <tex>e = (a(ab)^*)^* + (ba)^*</tex>.
1. Линеаризуем его путем добавления индекса к каждому символу:
:<tex>e'=(a_1(a_2b_3)^*)^*+(b_4a_5)^*</tex>.
2. Составим множества <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>.
3. Автомат локального языка <tex>L'=P'B^*\cap B^*D'\setminus B^*(B^2\setminus F')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>).
4. Получим автомат для <tex>L(e)</tex> удалив индексы, добавленные на первом этапе.
== См. также ==
