Изменения
Нет описания правки
{{Определение
|definition=
'''Граф Майхилла <tex>G</tex> (над алфавитом <tex>\Sigma</tex>)''' (англ. ''Myhill graph'') {{---}} [[Основные определения теории графов | ориентированный граф]], удовлетворяющий свойствам:
# Для каждой упорядоченной пары вершин <tex>v</tex> и <tex>u</tex> существует только одно ребро из <tex>v</tex> в <tex>u</tex>.
# Некоторые вершины обозначены начальными, а некоторые {{---}} конечными. Ребро может одновременно быть начальным и конечным.
Ребра, выходящие из стартового состояния обозначены различными символами, потому что они указывают на вершины, которые, по свойству 3, были отмечены различными символами в исходном автомате.
Если мы рассмотрим любое другое состояние <tex>s</tex>, то два перехода из <tex>s</tex> могут иметь одинаковые метки только в том случае, если в <tex>G</tex> оба ориентированных ребра идут в одну и ту же вершину. Но этого не может быть по свойтсву 1.
То есть <tex>A</tex> {{---}} [[Детерминированные_конечные_автоматы | ДКА, возможно, незаконченный]]. По построению он является стандартным локальным автоматом.
Теперь просто проверить, что <tex>L(A) = L(G)</tex>.
