Изменения
Нет описания правки
Символ <tex>c \in \Sigma</tex> назовем разрешенным, если им помечена вершина, являющая одновременно начальной и конечной.
Не пустая строка <tex>c_1c_2...\ldots 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>(c_i, c_{i+1})</tex>.
Язык <tex>L(G)</tex>, распознаваемый графом Майхилла, состоит из всех разрешенных строк из <tex>\Sigma^+</tex>.
Покажем, что графы Майхилла могут быть представлены в виде автоматов.
Пусть <tex>\mathcal{A } = (S, \Sigma, i, \delta, T)</tex> {{---}} [[Детерминированные_конечные_автоматы | ДКА]].
{{Определение
{{Определение
|definition=Язык <tex>L \subseteq A^*</tex> называется '''локальным языком''' (англ. ''local language''), если <tex>L \setminus \varepsilon</tex> может быть описан следующим образом: <br>
<center><tex>\exists P, S \subseteq A, N \subseteq A^2: L \setminus \varepsilon = (P A^* \cap A^* S) \setminus A^* N A^*</tex>.</center>
}}
{{Утверждение
|statement=Автомат Определенный таким образом автомат <tex>\mathcal{A}</tex> – {{---}} стандартный локальный автомат, распознающий <tex>L</tex>.
|proof=
Автомат является локальным поскольку для каждого состояния <tex>s</tex> и любого символа <tex>a</tex> <tex>\delta(s, a)</tex> либо неопределена либо равна <tex>a</tex>. По построению автомат является стандартным. Покажем, что <tex>L(\mathcal{A}) = L</tex>.<br>
