Изменения

Язык распознается графом Майхилла тогда и только тогда, когда он распознается стандартным локальным автоматом, стартовое состояние которого не является терминальным.

|proof=

Построим автомат А следующим образом:

* Добавим вершину ромбик в G с ребрами от ромбика к каждой стартовой вершине G, отметим вершину ромбик как стартовое состояние.

То есть А - ДКА, возможно, незаконченный. По построению он является стандартным локальным автоматом.

Теперь просто проверить, что L(A) = L(G).

Построим по нему граф Майхилла следующим образом:

* Отметим все состояния А, кроме стартового, input символами, стоящими на ребрах, входящих в эти состояния.

* Отметим все терминальные состояния как конечные вершины.

* Удалим вершину i и все ребра, исходящие из нее.

}}