Изменения
Нет описания правки
{{Определение
|definition= Автомат <tex>A</tex> называется '''локальным''' (англ. '''local automation'''), если для любого <tex>c</tex> из <tex>\Sigma</tex> множество <tex>\{\delta(s, c): s \in S\}</tex> содержит не более одного элемента.
}}
Пусть <tex>G</tex> {{---}} граф Майхилла.
Построим автомат <tex>A</tex> следующим образом:
* Добавим вершину <tex>\diamondDiamond</tex> в <tex>G</tex> с ребрами от <tex>\diamondDiamond</tex> к каждой стартовой вершине <tex>G</tex>; отметим вершину <tex>\diamondDiamond</tex> как стартовое состояние.
* Отметим конечные вершины как терминальные состояния.
* Отметим каждое ребро результирующего ориентированного графа символом, стоящим в вершине, на которою оно указывает.
