Изменения

{{Определение|definition=Графы '''Граф Майхилла<tex>G</tex> (над алфавитом <tex>\Sigma</tex>)''' (англ.=''Myhill graph'') {{---}} [[Основные определения теории графов | ориентированный граф]], удовлетворяющий свойствам:# Для каждой упорядоченной пары вершин <tex>v</tex> и <tex>u</tex> существует только одно ребро из <tex>v</tex> в <tex>u</tex>.# Некоторые вершины обозначены начальными, а некоторые {{---}} конечными. Ребро может одновременно быть начальным и конечным.# Вершины обозначены различными символами из конечного алфавита <tex>\Sigma</tex>, то есть мы можем обращаться к вершине по ее символу.}}

Граф Пусть <tex>G</tex> {{---}} граф Майхилла G (над алфавитом А) - ориентированный граф, удовлетворяющий свойствам:1. Для каждой упорядоченной пары вершин v1 и v2 существует только одно ребро из v1 в v2.2. Некоторые вершины обозначены начальными, а некоторые - конечными. Ребро может одновременно быть начальным и конечным.3. Вершины обозначены различными символами из конечного алфавита А, то есть мы можем обращаться к вершине по ее символу<tex>\Sigma</tex>.

Пусть G - граф Майхилла над алфавитом АСимвол <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>.

Не пустая строка a_1a_2...a_n из A* длиной не менее двух символовЯзык <tex>L(G)</tex>, называется разрешеннойраспознаваемый графом Майхилла, если символом a_1 отмечена стартовая вершина, а символом a_n - конечная, и для состоит из всех 1 разрешенных строк из <= i tex>\Sigma^+<= n-1 в G существует ребро a_i -/tex> a_{i+1}.

Язык LПокажем, что графы Майхилла могут быть представлены в виде автоматов. Пусть <tex>\mathcal{A} = (G)S, \Sigma, i, распознаваемый графом Майхилла\delta, состоит из всех разрешенных строк из A+T)</tex> {{---}} [[Детерминированные_конечные_автоматы | ДКА]].

Покажем, графы Майхилла могут быть представлены в виде автоматов. {{ОпределениеПусть |definition= Автомат <tex>\mathcal{A = }</tex> называется '''локальным''' (Sангл. ''local automaton'', A, i''Glushkov automaton''), если для любого <tex>c</tex> из <tex>\Sigma</tex> множество <tex>\{\delta(s, Tc) - ДКА, \mid s \in S\}</tex> содержит не обязательно законченныйболее одного элемента.}}

Автомат А называется локальным, если для любого a из {{Определение|definition=Локальный автомат <tex>\mathcal{A множество {s * a: s in S} содержит не более одного элемента. Автомат А </tex> называется '''стандартным локальным ''' автоматом(англ. ''standard local automation''), если в нем нет перехода в начальное состояние.}} Таким образом, автомат является локальным, если для каждого <tex>c</tex> из <tex>\Sigma</tex> нет переходов, отмеченных <tex>c</tex>, или если все они ведут в одно состояние.

{{Теорема. |id=th1|statement=Язык распознается графом Майхилла тогда и только тогда, когда он распознается стандартным локальным автоматом, стартовое состояние которого не является терминальным.Доказательство.|proof=(-<tex>\Rightarrow</tex>) :Пусть <tex>G </tex> {{- --}} граф Майхилла. :Построим автомат А <tex>\mathcal{A}</tex> следующим образом: :* Добавим вершину ромбик <tex>i</tex> в <tex>G </tex> с ребрами от ромбика <tex>i</tex> к каждой стартовой вершине <tex>G, </tex>; отметим вершину ромбик <tex>i</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, A\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>.  Пусть <tex>x = a_1 \ldots a_n \in L</tex>. Тогда <tex>a_1 \in P</tex>, <tex>a_n \in S</tex> и для каждого <tex>j</tex> <tex>a_j a_{j+1} \not \in N</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>x \in L(\mathcal{A})</tex>.  }} {{Утверждение|statement=Язык, распознаваемый локальным автоматом, является локальным.}} ==Алгоритм Глушкова=====Описание===Дано регулярное выражение <tex>e</tex>. Алгоритм Глушкова строит недетерминированный автомат, который распознает язык <tex>L(e)</tex>, распознаваемый <tex>e</tex>. Построение происходит в несколько шагов: * Линеаризация регулярного выражения. Каждый символ из алфавита, содержащийся в регулярном выражении, переименовывается таким образом, что каждый символ содержится в новом регулярном выражении не более одного раза. Пусть <tex>A</tex> {{---}} исходный алфавит, <tex>B</tex> {{---}} новый алфавит. * Вычисление множеств <tex>P(e'), S(e'), N(e')</tex>, где <tex>e'</tex> {{---}} линеаризованное регулярное выражение. <tex>P(e')</tex> {{---}} множество символов, с которых начинается слово из <tex>L(e')</tex>. <tex>S(e')</tex> {{---}} множество символов, на которые оканчивается слово из <tex>L(e')</tex> и <tex>N(e')</tex> {{---}} множество пар символов, которые встречаются в слове из <tex>L(e')</tex>. Более формально: <br><tex>P(e')=\{a\in B\mid aB^*\cap L(e')\ne\emptyset\}</tex>,<br><tex>S(e')=\{a\in B\mid B^*a\cap L(e')\ne\emptyset\}</tex>,<br><tex>N(e')=\{u\in B^2\mid B^*uB^*\cap L(e')\ne\emptyset\}</tex>. * Вычисление множества <tex>\Lambda(e')</tex> такого что <tex>\Lambda(e')=\{\varepsilon\}\cap L(e')</tex>. * Вычисление локального языка с заданными множествами и построение по нему автомата. * Делинеаризация, переименование каждого символа из <tex>B</tex> в соответствующий ему символ из <tex>A</tex>. ===Пример работы===[[Файл:Glushkov_lin_automata.jpg|frame|right|Автомат, построенный в ходе работы алгоритма Глушкова]] Рассмотрим регулярное выражение <tex>e = (a(ab)^*)^* + (ba)^*</tex>: * Линеаризуем его путем добавления индекса к каждому символу::<tex>e'=(a_1(a_2b_3)^*)^*+(b_4a_5)^*</tex>. * Составим множества <tex>P</tex>, <tex>S</tex>, и <tex>N</tex>::<tex>P(e')=\{a_1,b_4\}</tex>,<br />:<tex>S(e')=\{a_1,b_3,a_5\}</tex>,<br />:<tex>N(e')=\{a_1a_2, a_1a_1, a_2b_3, b_3a_1,b_3a_2,b_4a_5,a_5b_4\}</tex>. Так как пустое слово принадлежит языку, то <math>\Lambda(e')=\{\varepsilon\}</math>. * Автомат локального языка <tex>L'=P'B^*\cap B^*S'\setminus B^*(B^2\setminus N')B^*</tex> содержит начальное состояние, обозначенное как <tex>1</tex>, и состояния для каждого из пяти символов алфавита <tex>B=\{a_1, a_2, b_3, b_4, a_5\}</tex>.<br>В построенном автомате существует переход из <tex>1</tex> (соответствующего пустой строке) в два состояния из <tex>P'</tex>, переход из <tex>a</tex> в <tex>b</tex> если <tex>ab \in N'</tex>, три состояния <math>S'</math> терминальные (как и состояние <tex>1</tex>).  * Получим автомат для <tex>L(e)</tex>, удалив индексы, добавленные на первом этапе. == См. также ==* [[Контексты и синтаксические моноиды]] == Источники информации ==* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' {{---}} Введение в теорию автоматов, языков и вычислений* ''Mark V. Lawson'' {{---}} Finite Automata* [https://en.wikipedia.org/wiki/Glushkov's_construction_algorithm Wikipedia {{---}} Glushkov's construction algorithm] [[Категория: Теория формальных языков]][[Категория: Автоматы и регулярные языки]][[Категория: Другие автоматы]]