Изменения

'''Граф Майхилла <tex>G</tex> (над алфавитом <tex>\Sigma</tex>)''' (англ. ''Myhill graph'') {{---}} [[Основные определения теории графов | ориентированный граф]], удовлетворяющий свойствам:1. # Для каждой упорядоченной пары вершин <tex>v</tex> и <tex>u</tex> существует только одно ребро из <tex>v</tex> в <tex>u</tex>. 2. # Некоторые вершины обозначены начальными, а некоторые {{---}} конечными. Ребро может одновременно быть начальным и конечным. 3. # Вершины обозначены различными символами из конечного алфавита <tex>\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>a_i \rightarrow a_(c_i, c_{i+1})</tex>.

[[Файл:Myhill3.png|300px|thumb|right|Рисунок 2]]Рассмотрим детерменированный конечный автомат, представленный на рисунке 2. Не сложно проверитьПокажем, что он распознает тот же язык, что и граф на рисунке 1. Покажем, графы Майхилла могут быть представлены в виде автоматов. Пусть <tex>\mathcal{A } = (S, \Sigma, i, \delta, T)</tex> {{---}} [[Детерминированные_конечные_автоматы | ДКА]].

|definition= Автомат <tex>\mathcal{A}</tex> называется '''локальным''' (англ. ''local automaton'', 'local automation'Glushkov automaton''), если для любого <tex>c</tex> из <tex>\Sigma</tex> множество <tex>\{\delta(s, c): \mid s \in S\}</tex> содержит не более одного элемента.

|definition= Автомат Локальный автомат <tex>\mathcal{A}</tex> называется '''стандартным локальным''' автоматом (англ. '''standard loal local automation'''), если в нем нет перехода в начальное состояние.

:Пусть <tex>G</tex> {{---}} граф Майхилла. :Построим автомат <tex>\mathcal{A}</tex> следующим образом: :* Добавим вершину <tex>\Diamondi</tex> в <tex>G</tex> с ребрами от <tex>\Diamondi</tex> к каждой стартовой вершине <tex>G</tex>; отметим вершину <tex>\Diamondi</tex> как стартовое состояние.:* Отметим конечные вершины как терминальные состояния.:* Отметим каждое ребро результирующего ориентированного графа символом, стоящим в вершине, на которою оно указывает. :Переходы преобразуются следующим образом: [[Файл:Myhill1.png|150px]] :По построению стартовое состояние не является терминальным.  :Покажем, что полученный автомат конечен. :Ребра, выходящие из стартового состояния обозначены различными символами, потому что они указывают на вершины, которые, по свойству 3, были отмечены различными символами в исходном автомате.:Если мы рассмотрим любое другое состояние <tex> s </tex>, то два перехода из <tex> s </tex> могут иметь одинаковые метки только в том случае, если в <tex>G</tex> оба ориентированных ребра идут в одну и ту же вершину. Но этого не может быть по свойству 1. :То есть <tex>\mathcal{A}</tex> {{---}} [[Детерминированные_конечные_автоматы | ДКА]]. По построению он является стандартным локальным автоматом. :Теперь просто проверить, что <tex>L(\mathcal{A}) = L(G) </tex>. <tex> \Leftarrow </tex> :Пусть <tex> \mathcal{A} = (S, \Sigma, i, \delta, T) </tex> {{---}} стандартный локальный автомат, стартовое состояние которого не является терминальным.:Построим по нему граф Майхилла следующим образом::* Отметим все состояния <tex> \mathcal{A} </tex>, кроме стартового, <tex> input </tex> символами, стоящими на ребрах, входящих в эти состояния. :* Сотрем все метки на ребрах <tex> \mathcal{A} </tex>.:* Отметим все состояния <tex> s </tex> как начальные вершины, если существует переход из <tex> i </tex> в <tex> s </tex>:* Отметим все терминальные состояния как конечные вершины.:* Удалим вершину <tex> i </tex> и все ребра, исходящие из нее.:Назовем полученный граф <tex> G </tex> {{---}} он будет графом Майхилла по построению. Легко проверить, что <tex> L(G) = L(\mathcal{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>. Недетерминированный автомат на рисунке 2 является локальным автоматом и распознает тот же самый язык. ==Локальный язык==Рассмотрим язык, распознаваемый стандартным локальным автоматом. {{Определение|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>}} Другими словами, непустое слово принадлежит локальному языку, если оно начинается с символа из <tex>P</tex>, оканчивается на символ из <tex>S</tex> и не содержит пары символов из множества <tex>N</tex>. Пусть <tex>L = (P A^* \cap A^* S) \setminus A^* N A^*</tex> {{---}} локальный язык. Определим автомат <tex>\mathcal{A}</tex> следующим образом:* набор состояний <tex>Q = A \cup \{ \varepsilon \}</tex>,* начальное состояние <tex>\varepsilon</tex>,* терминальные состояния <tex>S</tex>,* <tex>\delta(\varepsilon, a) = a</tex> если <tex>a \in P</tex> и <tex>\delta(a, b) = b</tex> если <tex>ab \not\in N</tex>.Если <tex>L</tex> содержит пустую строку, то множество терминальных состояний <tex>\mathcal{A}</tex> {{---}} <tex>S \cup \{ \varepsilon \}</tex>.

{{Утверждение|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>Пусть <tex>x = a_1 \ldots a_n \in L(\mathcal{A})</tex>. Тогда в автомате существует путь: <br>:<tex>\varepsilon \xrightarrow{a_1} a_1 \xrightarrow{a_2} a_2 \ldots a_{n-1} \xrightarrow{a_n} a_n</tex>.Здесь <tex>a_n</tex> {{---}} терминальное состояние не является терминальным, <tex>a_n \in S</tex>. Переход из <tex>\varepsilon</tex> в <tex>a_1</tex> определен, поэтому <tex>a_1 \in P</tex>. Для каждого <tex>j: 1 \leqslant j \leqslant n - 1</tex> факт, что переход <tex>a_j \rightarrow a_{j+1}</tex> существует, означает что <tex>a_j a_{j+1} \not \in N</tex>. Следовательно, <tex>x \in L</tex>.

Покажем, что полученный автомат конечен. Ребра, выходящие из стартового состояния обозначены различными символами, потому что они указывают на вершины, которые, по свойству 3, были отмечены различными символами в исходном автоматеПусть <tex>x = a_1 \ldots a_n \in L</tex>.Если мы рассмотрим любое другое состояние Тогда <tex>sa_1 \in P</tex>, то два перехода из <tex>sa_n \in S</tex> могут иметь одинаковые метки только в том случае, если в и для каждого <tex>Gj</tex> оба ориентированных ребра идут в одну и ту же вершину. Но этого не может быть по свойтсву <tex>a_j a_{j+1} \not \in N</tex>. То есть Следовательно в автомате существует путь из начального состояния в терминальное: <texbr>A:</tex> \varepsilon \xrightarrow{a_1} a_1 \xrightarrow{a_2} a_2 \ldots a_{n---1}\xrightarrow{a_n} ДКА, возможно, незаконченный. По построению он является стандартным локальным автоматомa_n</tex>. Теперь просто проверитьСледовательно, что <tex>x \in L(\mathcal{A) = L(G})</tex>.

Пусть <tex>A = (S, \Sigma, i, \delta, T)</tex> {{---}} стандартный локальный автомат, стартовое состояние которого не является терминальным.УтверждениеПостроим по нему граф Майхилла следующим образом:* Отметим все состояния <tex>A</tex>|statement=Язык, кроме стартовогораспознаваемый локальным автоматом, <tex>input</tex> символами, стоящими на ребрах, входящих в эти состояния. * Сотрем все метки на ребрах <tex>A</tex>.* Отметим все состояния <tex>s</tex> как начальные вершины, если существует переход из <tex>i</tex> в <tex>s</tex>* Отметим все терминальные состояния как конечные вершины.* Удалим вершину <tex>i</tex> и все ребра, исходящие из нее.Назовем полученный граф <tex>G</tex> {{---}} он будет графом Майхилла по построению. Легко проверить, что <tex>L(G) = L(A)</tex>является локальным.