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