Изменения

Не пустая строка <tex>c_1c_2...\ldots c_n</tex> из <tex>\Sigma^*</tex> длиной не менее двух символов, называется разрешенной, если символом <tex>c_1</tex> отмечена стартовая вершина, а символом <tex>c_n</tex> {{---}} конечная, и для всех <tex>1 \leqslant i \leqslant n - 1</tex> в <tex>G</tex> существует ребро <tex>(c_i, c_{i+1})</tex>.

Пусть <tex>\mathcal{A } = (S, \Sigma, i, \delta, T)</tex> {{---}} [[Детерминированные_конечные_автоматы | ДКА]].

:Построим автомат <tex>\mathcal{A}</tex> следующим образом: :* Добавим вершину <tex>\Diamondi</tex> в <tex>G</tex> с ребрами от <tex>\Diamondi</tex> к каждой стартовой вершине <tex>G</tex>; отметим вершину <tex>\Diamondi</tex> как стартовое состояние.

:Если мы рассмотрим любое другое состояние <tex>s</tex>, то два перехода из <tex>s</tex> могут иметь одинаковые метки только в том случае, если в <tex>G</tex> оба ориентированных ребра идут в одну и ту же вершину. Но этого не может быть по свойтсву свойству 1. :То есть <tex>\mathcal{A}</tex> {{---}} [[Детерминированные_конечные_автоматы | ДКА]]. По построению он является стандартным локальным автоматом. :Теперь просто проверить, что <tex>L(\mathcal{A}) = L(G)</tex>.

<tex>\Leftarrow</tex>

:Пусть <tex>\mathcal{A } = (S, \Sigma, i, \delta, T)</tex> {{---}} стандартный локальный автомат, стартовое состояние которого не является терминальным.

:* Отметим все состояния <tex>\mathcal{A} </tex>, кроме стартового, <tex>input</tex> символами, стоящими на ребрах, входящих в эти состояния. :* Сотрем все метки на ребрах <tex>\mathcal{A} </tex>.:* Отметим все состояния <tex>s</tex> как начальные вершины, если существует переход из <tex>i</tex> в <tex>s</tex>

:* Удалим вершину <tex>i</tex> и все ребра, исходящие из нее.:Назовем полученный граф <tex>G</tex> {{---}} он будет графом Майхилла по построению. Легко проверить, что <tex>L(G) = L(\mathcal{A})</tex>.

<center><tex>\exists P, S \subseteq A, N \subseteq A^2: L \setminus \varepsilon = (P A^* \cap A^* S) \setminus A^* N A^*</tex>.</center>

|statement=Автомат Определенный таким образом автомат <tex>\mathcal{A}</tex> – {{---}} стандартный локальный автомат, распознающий <tex>L</tex>.

Автомат является локальным поскольку для каждого состояния <tex>s</tex> и любого символа <tex>a</tex> <tex>\delta(s, a)</tex> либо неопределена либо равна <tex>a</tex>. По построению автомат является стандартным. <br>Покажем, что <tex>L(\mathcal{A}) = L</tex>. <br>Пусть <tex>x = a_1 \ldots a_n \in L(\mathcal{A})</tex>. Тогда в автомате существует путь: <br>

Здесь <tex>a_n</tex> {{---}} терминальное состояние, <tex>a_n \in S</tex>. Переход из <tex>\varepsilon</tex> в <tex>a_1</tex> определен, поэтому <tex>a_1 \in P</tex>. Для каждого <tex>j</tex> такого что <tex>: 1 \leqslant j \leqslant n - 1</tex> факт, что переход <tex>a_j \rightarrow a_{j+1}</tex> существует, означает что <tex>a_j a_{j+1} \not \in N</tex>.Следовательно, <tex>x \in L</tex>.  Пусть <tex>x = a_1 \ldots a_n \in L</tex>. Тогда <tex>a_1 \in P</tex>, <tex>a_n \in S</tex> и для каждого <tex>j</tex> <tex>a_j a_{j+1} \not \in N</tex>. Следовательно в автомате существует путь из начального состояния в терминальное: <br>:<tex>\varepsilon \xrightarrow{a_1} a_1 \xrightarrow{a_2} a_2 \ldots a_{n-1} \xrightarrow{a_n} a_n</tex>.Следовательно, <tex>x \in L(\mathcal{A})</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>. 

Рассмотрим регулярное выражение <tex>e = (a(ab)^*)^* + (ba)^*</tex>.:

1. * Линеаризуем его путем добавления индекса к каждому символу:

2. * Составим множества <tex>P</tex>, <tex>S</tex>, и <tex>N</tex>:

3. * Автомат локального языка <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>

4. * Получим автомат для <tex>L(e)</tex>, удалив индексы, добавленные на первом этапе.

* ''Хопкрофт Д., Мотвани Р., Ульман Д. '' {{---}} Введение в теорию автоматов, языков и вычислений* ''Mark V. Lawson '' {{---}} Finite Automata