Изменения
Нет описания правки
Не пустая строка <tex>c_1c_2...c_n</tex> из <tex>\Sigma^*</tex> длиной не менее двух символов, называется разрешенной, если символом <tex>c_1</tex> отмечена стартовая вершина, а символом <tex>c_n</tex> {{---}} конечная, и для всех <tex>1 <= i <= n - 1</tex> в <tex>G</tex> существует ребро <tex>a_i \rightarrow a_{i+1}</tex>.
Язык <tex>L(G)</tex>, распознаваемый графом Майхилла, состоит из всех разрешенных строк из A <tex>\Sigma^+</tex>.
Покажем, графы Майхилла могут быть представлены в виде автоматов.
Пусть M <tex>A = (S, A \Sigma, i, \delta, T) </tex> {{---}} ДКА, не обязательно законченный.
{{Определение
|definition= Автомат M <tex>A</tex> называется '''локальным''' (англ. '''local automation'''), если для любого a <tex>c</tex> из A <tex>\Sigma</tex> множество <tex>{s * a: s \in S} </tex> содержит не более одного элемента.
}}
{{Определение
|definition= Автомат M <tex>A</tex> называется '''стандартным локальным''' автоматом (англ. '''standard loal automation'''), если в нем нет перехода в начальное состояние.
}}
Таким образом, автомат является локальным, если для каждого а <tex>c</tex> из А <tex>\Sigma</tex> нет переходов, отмеченных а<tex>c</tex>, или если все они в одно состояние.
Покажем, что граф Майхилла может быть преобразован в стандартный локальный автомат таким образом, что распознаваемый им язык не изменится.
<tex>\Rightarrow</tex>
Пусть <tex>G </tex> {{---}} граф Майхилла. Построим автомат <tex>А </tex> следующим образом: * Добавим вершину ромбик в <tex>G </tex> с ребрами от ромбика к каждой стартовой вершине <tex>G</tex>, отметим вершину ромбик как стартовое состояние.
* Отметим конечные вершины как терминальные состояния.
* Отметим каждое ребро результирующего ориентированного графа символом, стоящим в вершине, на которою оно указывает.
Покажем, что полученный автомат конечен.
Ребра, выходящие из стартового состояния обозначены различными символами, потому что они указывают на вершины, которые, по свойству 3, были отмечены различными символами в исходном автомате.
Если мы рассмотрим любое другое состояние <tex>s</tex>, то два перехода из <tex>s </tex> могут иметь одинаковые метки только в том случае, если в <tex>G </tex> оба ориентированных ребра идут в одну и ту же вершину. Но этого не может быть по свойтсву 1. То есть <tex>А </tex> {{- --}} ДКА, возможно, незаконченный. По построению он является стандартным локальным автоматом. Теперь просто проверить, что <tex>L(A) = L(G)</tex>.
<tex>\Leftarrow</tex>
Пусть <tex>A = (S, A\Sigma, i, \delta, T) </tex> {{---}} стандартный локальный автомат, стартовое состояние которого не является терминальным.
Построим по нему граф Майхилла следующим образом:
* Отметим все состояния <tex>А</tex>, кроме стартового, <tex>input </tex> символами, стоящими на ребрах, входящих в эти состояния. * Сотрем все метки на ребрах <tex>А</tex>.* Отметим все состояния <tex>s </tex> как начальные вершины, если существует переход из <tex>i </tex> в <tex>s</tex>
* Отметим все терминальные состояния как конечные вершины.
* Удалим вершину <tex>i </tex> и все ребра, исходящие из нее.Назовем полученный граф <tex>G </tex> {{---}} он будет графом Майхилла по построению. Легко проверить, что <tex>L(G) = L(A)</tex>.
}}
