Изменения

}}

Рассмотрим пример (рис. 1). Этот граф может быть использован для распознавания строк над алфавитом <tex>\Sigma = \{a, b\}</tex>. По определению, язык, распознаваемый данным графом, состоит из непустых строк, начинающихся и заканчивающихся на <tex>a</tex>; он имеет вид: <tex>L = (a \Sigma^* \cap \Sigma^* a) \setminus \Sigma^* b^2 \Sigma^*</tex>.

Язык <tex>L(G)</tex>, распознаваемый графом Майхилла, состоит из всех разрешенных строк из <tex>\Sigma^+</tex>.

Рассмотрим детерменированный конечный автомат, представленный на рисунке 2.

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