Изменения
Нет описания правки
1. Для каждой упорядоченной пары вершин <tex>v</tex> и <tex>u</tex> существует только одно ребро из <tex>v</tex> в <tex>u</tex>.
2. Некоторые вершины обозначены начальными, а некоторые {{- --}} конечными. Ребро может одновременно быть начальным и конечным.
3. Вершины обозначены различными символами из конечного алфавита <tex>\Sigma</tex>, то есть мы можем обращаться к вершине по ее символу.
Пусть <tex>G</tex> {{---}} граф Майхилла над алфавитом <tex>\Sigma</tex>.
Символ <tex>c</tex>, <tex>c \in \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>c</tex> из <tex>\Sigma</tex> нет переходов, отмеченных <tex>c</tex>, или если все они ведут в одно состояние.
Покажем, что граф Майхилла может быть преобразован в стандартный локальный автомат таким образом, что распознаваемый им язык не изменится.
