Изменения
Нет описания правки
Пусть <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>.
* Отметим конечные вершины как терминальные состояния.
* Отметим каждое ребро результирующего ориентированного графа символом, стоящим в вершине, на которою оно указывает.
Переходы преобразуются следующим образом: [[Файл:Myhill1.png|150px]]
По построению стартовое состояние не является терминальным.
