188
правок
Изменения
Нет описания правки
{{Определение
|definition=Язык <tex>L \subseteq A^*</tex> называется '''локальным языком''' (англ. ''local language''), если <tex>L \backslash \varepsilon</tex> может быть описан следующим образом: <br>
<tex>\exists P, S \subseteq A, N \subseteq A^2: L \backslash \varepsilon = (P A^* \bigcap cap A^* S) \backslash A^* N A^*</tex>.
}}
Другими словами, непустое слово принадлежит локальному языку, если оно начинается с символа из <tex>P</tex>, оканчивается на символ из <tex>S</tex> и не содержит пары символов из множества <tex>N</tex>.
Пусть <tex>L = (P A^* \bigcap cap A^* S) \backslash A^* N A^*</tex> – {{---}} локальный язык. Определим автомат <tex>\mathcal{A}</tex> следующим образом:* набор состояний <tex>Q = A \bigcup cup \{ \varepsilon \}</tex>,
* начальное состояние <tex>\varepsilon</tex>,
* терминальные состояния <tex>S</tex>,
* <tex>\delta(\varepsilon, a) = a</tex> если <tex>a \in P</tex> и <tex>\delta(a, b) = b</tex> если <tex>ab \not\in N</tex>.
Если <tex>L</tex> содержит пустую строку, то множество терминальных состояний <tex>\mathcal{A}</tex> – {{---}} <tex>S \bigcup cup \{ \varepsilon \}</tex>.
{{Утверждение
|statement=Язык, распознаваемый локальным автоматом, является локальным.
}}
==Алгоритм Глушкова==
===Описание===
Дано регулярное выражение <tex>e</tex>. Алгоритм Глушкова строит недетерминированный автомат, который распознает язык <tex>L(e)</tex>, распознаваемый <tex>e</tex>. Построение происходит в несколько шагов:
# Линеаризация регулярного выражения. Каждый символ из алфавита, содержащийся в регулярном выражении, переименовывается таким образом, что каждый символ содержится в новом регулярном выражении не более одного раза. Пусть <tex>A</tex> {{---}} исходный алфавит, <tex>B</tex> {{---}} новый алфавит.
# Вычисление множеств <tex>P(e'), D(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>.
===Пример работы===
== См. также ==
