Изменения

'''Граф Майхилла <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>.

Покажем, что графы Майхилла могут быть представлены в виде автоматов. Пусть <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>.

ГрафМайхилла, изображенный на рисунке 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>\Sigmadelta(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\Sigma}</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 \SigmaB^* b(B^2 \Sigmasetminus 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]

Рассмотрим детерменированный конечный автомат, представленный на рисунке 2. [[Категория: Теория формальных языков]]Не сложно проверить, что он распознает тот же язык, что [[Категория: Автоматы и граф на рисунке 1.регулярные языки]][[Категория: Другие автоматы]]