Изменения
Нет описания правки
Пусть <tex>G</tex> {{---}} граф Майхилла.
Построим автомат <tex>АA</tex> следующим образом:
* Добавим вершину ромбик в <tex>G</tex> с ребрами от ромбика к каждой стартовой вершине <tex>G</tex>, отметим вершину ромбик как стартовое состояние.
* Отметим конечные вершины как терминальные состояния.
* Отметим каждое ребро результирующего ориентированного графа символом, стоящим в вершине, на которою оно указывает.
По построению стартовое состояние не является терминальным.
Покажем, что полученный автомат конечен.
Ребра, выходящие из стартового состояния обозначены различными символами, потому что они указывают на вершины, которые, по свойству 3, были отмечены различными символами в исходном автомате.
Если мы рассмотрим любое другое состояние <tex>s</tex>, то два перехода из <tex>s</tex> могут иметь одинаковые метки только в том случае, если в <tex>G</tex> оба ориентированных ребра идут в одну и ту же вершину. Но этого не может быть по свойтсву 1.
То есть <tex>АA</tex> {{---}} ДКА, возможно, незаконченный. По построению он является стандартным локальным автоматом.
Теперь просто проверить, что <tex>L(A) = L(G)</tex>.
Пусть <tex>A = (S, \Sigma, i, \delta, T)</tex> {{---}} стандартный локальный автомат, стартовое состояние которого не является терминальным.
Построим по нему граф Майхилла следующим образом:
* Отметим все состояния <tex>АA</tex>, кроме стартового, <tex>input</tex> символами, стоящими на ребрах, входящих в эти состояния.
* Сотрем все метки на ребрах <tex>А</tex>.
* Отметим все состояния <tex>s</tex> как начальные вершины, если существует переход из <tex>i</tex> в <tex>s</tex>
