Изменения
Нет описания правки
3. Вершины обозначены различными символами из конечного алфавита <tex>\Sigma</tex>, то есть мы можем обращаться к вершине по ее символу.
}}
Пусть <tex>G</tex> {{---}} граф Майхилла над алфавитом <tex>\Sigma</tex>.
Язык <tex>L(G)</tex>, распознаваемый графом Майхилла, состоит из всех разрешенных строк из <tex>\Sigma^+</tex>.
Покажем, графы Майхилла могут быть представлены в виде автоматов.
Назовем полученный граф <tex>G</tex> {{---}} он будет графом Майхилла по построению. Легко проверить, что <tex>L(G) = L(A)</tex>.
}}
==Пример==
{| cellpadding="3" style="margin-left: auto; margin-right: auto;"
| [[Файл:Myhill2.png|300px|thumb|right|Рисунок 1]]
| [[Файл:Myhill3.png|200px|thumb|right|Рисунок 2]]
|}
Граф, изображенный на рисунке 1 может быть использован для распознавания строк над алфавитом <tex>\Sigma = \{a, b\}</tex>. По определению, язык, распознаваемый данным графом, состоит из непустых строк, начинающихся и заканчивающихся на <tex>a</tex>; он имеет вид: <tex>L = (a \Sigma^* \cap \Sigma^* a) \setminus \Sigma^* b^2 \Sigma^*</tex>.
Рассмотрим детерменированный конечный автомат, представленный на рисунке 2.
Не сложно проверить, что он распознает тот же язык, что и граф на рисунке 1.
