Изменения

:* Добавим вершину <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>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>.

# * Линеаризация регулярного выражения. Каждый символ из алфавита, содержащийся в регулярном выражении, переименовывается таким образом, что каждый символ содержится в новом регулярном выражении не более одного раза. Пусть <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