Изменения

|definition= Автомат <tex>\mathcal{A}</tex> называется '''локальным''' (англ. ''local automationautomaton'', ''Glushkov automaton''), если для любого <tex>c</tex> из <tex>\Sigma</tex> множество <tex>\{\delta(s, c) \mid s \in S\}</tex> содержит не более одного элемента.

|definition= Автомат Локальный автомат <tex>\mathcal{A}</tex> называется '''стандартным локальным''' автоматом (англ. ''standard local automation''), если в нем нет перехода в начальное состояние.

:Пусть <tex>G</tex> {{---}} граф Майхилла. :Построим автомат <tex>A</tex> следующим образом: :* Добавим вершину <tex>\Diamond</tex> в <tex>G</tex> с ребрами от <tex>\Diamond</tex> к каждой стартовой вершине <tex>G</tex>; отметим вершину <tex>\Diamond</tex> как стартовое состояние.:* Отметим конечные вершины как терминальные состояния.:* Отметим каждое ребро результирующего ориентированного графа символом, стоящим в вершине, на которою оно указывает. :Переходы преобразуются следующим образом: [[Файл:Myhill1.png|150px]]

:По построению стартовое состояние не является терминальным.

:Покажем, что полученный автомат конечен. :Ребра, выходящие из стартового состояния обозначены различными символами, потому что они указывают на вершины, которые, по свойству 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>A</tex>.:* Отметим все состояния <tex>s</tex> как начальные вершины, если существует переход из <tex>i</tex> в <tex>s</tex>:* Отметим все терминальные состояния как конечные вершины.:* Удалим вершину <tex>i</tex> и все ребра, исходящие из нее.:Назовем полученный граф <tex>G</tex> {{---}} он будет графом Майхилла по построению. Легко проверить, что <tex>L(G) = L(A)</tex>.

ГрафМайхилла, изображенный на рисунке 1 может быть использован для распознавания строк над алфавитом <tex>\Sigma = \{a, b\}</tex>. По определению, язык, распознаваемый данным графом, состоит из непустых строк, начинающихся и заканчивающихся на <tex>a</tex>.

Рассмотрим детерменированный конечный Недетерминированный автомат, представленный на рисунке 2. Не сложно проверить, что он является локальным автоматом и распознает тот же самый язык, что и граф на рисунке 1.