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