188
правок
Изменения
Нет описания правки
:Пусть <tex>G</tex> {{---}} граф Майхилла.
:Построим автомат <tex>\mathcal{A}</tex> следующим образом:
:* Добавим вершину <tex>\Diamond</tex> в <tex>G</tex> с ребрами от <tex>\Diamond</tex> к каждой стартовой вершине <tex>G</tex>; отметим вершину <tex>\Diamond</tex> как стартовое состояние.
:* Отметим конечные вершины как терминальные состояния.
:Ребра, выходящие из стартового состояния обозначены различными символами, потому что они указывают на вершины, которые, по свойству 3, были отмечены различными символами в исходном автомате.
:Если мы рассмотрим любое другое состояние <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>.
}}
