Локальные автоматы — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Пример работы)
(Алгоритм Глушкова)
 
(не показано 16 промежуточных версий 3 участников)
Строка 13: Строка 13:
 
Символ <tex>c \in \Sigma</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>(c_i, c_{i+1})</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>L(G)</tex>, распознаваемый графом Майхилла, состоит из всех разрешенных строк из  <tex>\Sigma^+</tex>.
  
 
Покажем, что графы Майхилла могут быть представлены в виде автоматов.  
 
Покажем, что графы Майхилла могут быть представлены в виде автоматов.  
Пусть <tex>A = (S,  \Sigma, i, \delta, T)</tex> {{---}} [[Детерминированные_конечные_автоматы | ДКА]].
+
Пусть <tex>\mathcal{A} = (S,  \Sigma, i, \delta, T)</tex> {{---}} [[Детерминированные_конечные_автоматы | ДКА]].
  
 
{{Определение
 
{{Определение
|definition= Автомат <tex>A</tex> называется '''локальным''' (англ. ''local automation''), если для любого <tex>c</tex> из  <tex>\Sigma</tex> множество <tex>\{\delta(s, c) \mid s \in S\}</tex> содержит не более одного элемента.  
+
|definition= Автомат <tex>\mathcal{A}</tex> называется '''локальным''' (англ. ''local automaton'', ''Glushkov automaton''), если для любого <tex>c</tex> из  <tex>\Sigma</tex> множество <tex>\{\delta(s, c) \mid s \in S\}</tex> содержит не более одного элемента.  
 
}}
 
}}
  
 
{{Определение
 
{{Определение
|definition= Автомат <tex>A</tex> называется '''стандартным локальным''' автоматом (англ. ''standard local automation''), если в нем нет перехода в начальное состояние.
+
|definition=Локальный автомат <tex>\mathcal{A}</tex> называется '''стандартным локальным''' автоматом (англ. ''standard local automation''), если в нем нет перехода в начальное состояние.
 
}}
 
}}
  
Строка 39: Строка 39:
 
<tex>\Rightarrow</tex>
 
<tex>\Rightarrow</tex>
  
Пусть <tex>G</tex> {{---}} граф Майхилла.  
+
:Пусть <tex>G</tex> {{---}} граф Майхилла.  
Построим автомат <tex>A</tex> следующим образом:  
+
:Построим автомат <tex>\mathcal{A}</tex> следующим образом:  
* Добавим вершину <tex>\Diamond</tex> в <tex>G</tex> с ребрами от <tex>\Diamond</tex> к каждой стартовой вершине <tex>G</tex>; отметим вершину <tex>\Diamond</tex> как стартовое состояние.
+
:* Добавим вершину <tex>i</tex> в <tex>G</tex> с ребрами от <tex>i</tex> к каждой стартовой вершине <tex>G</tex>; отметим вершину <tex>i</tex> как стартовое состояние.
* Отметим конечные вершины как терминальные состояния.
+
:* Отметим конечные вершины как терминальные состояния.
* Отметим каждое ребро результирующего ориентированного графа символом, стоящим в вершине, на которою оно указывает.  
+
:* Отметим каждое ребро результирующего ориентированного графа символом, стоящим в вершине, на которою оно указывает.  
Переходы преобразуются следующим образом: [[Файл:Myhill1.png|150px]]
+
:Переходы преобразуются следующим образом: [[Файл:Myhill1.png|150px]]
  
По построению стартовое состояние не является терминальным.  
+
:По построению стартовое состояние не является терминальным.  
  
Покажем, что полученный автомат конечен.  
+
:Покажем, что полученный автомат конечен.  
Ребра, выходящие из стартового состояния обозначены различными символами, потому что они указывают на вершины, которые, по свойству 3, были отмечены различными символами в исходном автомате.
+
:Ребра, выходящие из стартового состояния обозначены различными символами, потому что они указывают на вершины, которые, по свойству 3, были отмечены различными символами в исходном автомате.
Если мы рассмотрим любое другое состояние <tex>s</tex>, то два перехода из <tex>s</tex> могут иметь одинаковые метки только в том случае, если в <tex>G</tex> оба ориентированных ребра идут в одну и ту же вершину. Но этого не может быть по свойтсву 1.  
+
:Если мы рассмотрим любое другое состояние <tex> s </tex>, то два перехода из <tex> s </tex> могут иметь одинаковые метки только в том случае, если в <tex>G</tex> оба ориентированных ребра идут в одну и ту же вершину. Но этого не может быть по свойству 1.  
То есть <tex>A</tex> {{---}} [[Детерминированные_конечные_автоматы | ДКА]]. По построению он является стандартным локальным автоматом.  
+
:То есть <tex>\mathcal{A}</tex> {{---}} [[Детерминированные_конечные_автоматы | ДКА]]. По построению он является стандартным локальным автоматом.  
Теперь просто проверить, что <tex>L(A) = L(G)</tex>.
+
:Теперь просто проверить, что <tex>L(\mathcal{A}) = L(G) </tex>.
  
<tex>\Leftarrow</tex>
+
<tex> \Leftarrow </tex>
  
Пусть <tex>A = (S, \Sigma, i, \delta, T)</tex> {{---}} стандартный локальный автомат, стартовое состояние которого не является терминальным.
+
:Пусть <tex> \mathcal{A} = (S, \Sigma, i, \delta, T) </tex> {{---}} стандартный локальный автомат, стартовое состояние которого не является терминальным.
Построим по нему граф Майхилла следующим образом:
+
:Построим по нему граф Майхилла следующим образом:
* Отметим все состояния <tex>A</tex>, кроме стартового, <tex>input</tex> символами, стоящими на ребрах, входящих в эти состояния.  
+
:* Отметим все состояния <tex> \mathcal{A} </tex>, кроме стартового, <tex> input </tex> символами, стоящими на ребрах, входящих в эти состояния.  
* Сотрем все метки на ребрах <tex>A</tex>.
+
:* Сотрем все метки на ребрах <tex> \mathcal{A} </tex>.
* Отметим все состояния <tex>s</tex> как начальные вершины, если существует переход из <tex>i</tex> в <tex>s</tex>
+
:* Отметим все состояния <tex> s </tex> как начальные вершины, если существует переход из <tex> i </tex> в <tex> s </tex>
* Отметим все терминальные состояния как конечные вершины.
+
:* Отметим все терминальные состояния как конечные вершины.
* Удалим вершину <tex>i</tex> и все ребра, исходящие из нее.
+
:* Удалим вершину <tex> i </tex> и все ребра, исходящие из нее.
Назовем полученный граф <tex>G</tex> {{---}} он будет графом Майхилла по построению. Легко проверить, что <tex>L(G) = L(A)</tex>.
+
:Назовем полученный граф <tex> G </tex> {{---}} он будет графом Майхилла по построению. Легко проверить, что <tex> L(G) = L(\mathcal{A}) </tex>.
 
}}
 
}}
  
Строка 72: Строка 72:
 
|}
 
|}
  
Граф, изображенный на рисунке 1 может быть использован для распознавания строк над алфавитом <tex>\Sigma = \{a, b\}</tex>. По определению, язык, распознаваемый данным графом, состоит из непустых строк, начинающихся и заканчивающихся на <tex>a</tex>.
+
Граф Майхилла, изображенный на рисунке 1 может быть использован для распознавания строк над алфавитом <tex>\Sigma = \{a, b\}</tex>. По определению, язык, распознаваемый данным графом, состоит из непустых строк, начинающихся и заканчивающихся на <tex>a</tex>.
  
Рассмотрим детерменированный конечный автомат, представленный на рисунке 2.
+
Недетерминированный автомат на рисунке 2 является локальным автоматом и распознает тот же самый язык.
Не сложно проверить, что он распознает тот же язык, что и граф на рисунке 1.
 
  
 
==Локальный язык==
 
==Локальный язык==
 
Рассмотрим язык, распознаваемый стандартным локальным автоматом.  
 
Рассмотрим язык, распознаваемый стандартным локальным автоматом.  
 
{{Определение
 
{{Определение
|definition=Язык <tex>L \subseteq A^*</tex> называется '''локальным языком''' (англ. ''local language''), если <tex>L \backslash \varepsilon</tex> может быть описан следующим образом:  <br>
+
|definition=Язык <tex>L \subseteq A^*</tex> называется '''локальным языком''' (англ. ''local language''), если <tex>L \setminus \varepsilon</tex> может быть описан следующим образом:  <br>
<tex>\exists P, S \subseteq A, N \subseteq A^2: L \backslash \varepsilon = (P A^* \cap A^* S) \backslash A^* N A^*</tex>.
+
<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>P</tex>, оканчивается на символ из <tex>S</tex> и не содержит пары символов из множества <tex>N</tex>.
  
Пусть <tex>L = (P A^* \cap A^* S) \backslash A^* N A^*</tex> {{---}} локальный язык. Определим автомат <tex>\mathcal{A}</tex> следующим образом:
+
Пусть <tex>L = (P A^* \cap A^* S) \setminus A^* N A^*</tex> {{---}} локальный язык. Определим автомат <tex>\mathcal{A}</tex> следующим образом:
 
* набор состояний <tex>Q = A \cup \{ \varepsilon \}</tex>,
 
* набор состояний <tex>Q = A \cup \{ \varepsilon \}</tex>,
 
* начальное состояние <tex>\varepsilon</tex>,
 
* начальное состояние <tex>\varepsilon</tex>,
Строка 94: Строка 93:
  
 
{{Утверждение
 
{{Утверждение
|statement=Автомат <tex>\mathcal{A}</tex> стандартный локальный автомат, распознающий <tex>L</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>.
 +
 
 
}}
 
}}
  
Строка 104: Строка 113:
 
===Описание===
 
===Описание===
 
Дано регулярное выражение <tex>e</tex>. Алгоритм Глушкова строит недетерминированный автомат, который распознает язык <tex>L(e)</tex>, распознаваемый <tex>e</tex>. Построение происходит в несколько шагов:
 
Дано регулярное выражение <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>A</tex> {{---}} исходный алфавит, <tex>B</tex> {{---}} новый алфавит.
# Вычисление множества <tex>\Lambda(e')</tex> такого что <tex>\Lambda(e')=\{\varepsilon\}\cap L(e')</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>B</tex> в соответствующий ему символ из <tex>A</tex>.
+
 
 +
* Вычисление множества <tex>\Lambda(e')</tex> такого что <tex>\Lambda(e')=\{\varepsilon\}\cap L(e')</tex>.
 +
 
 +
* Вычисление локального языка с заданными множествами и построение по нему автомата.
 +
 
 +
* Делинеаризация, переименование каждого символа из <tex>B</tex> в соответствующий ему символ из <tex>A</tex>.
 +
 
 
===Пример работы===
 
===Пример работы===
Рассмотрим регулярное выражение <tex>e = (a(ab)^*)^* + (ba)^*</tex>.
+
[[Файл:Glushkov_lin_automata.jpg|frame|right|Автомат, построенный в ходе работы алгоритма Глушкова]]
 +
 
 +
Рассмотрим регулярное выражение <tex>e = (a(ab)^*)^* + (ba)^*</tex>:
  
1. Линеаризуем его путем добавления индекса к каждому символу:
+
* Линеаризуем его путем добавления индекса к каждому символу:
 
:<tex>e'=(a_1(a_2b_3)^*)^*+(b_4a_5)^*</tex>.
 
:<tex>e'=(a_1(a_2b_3)^*)^*+(b_4a_5)^*</tex>.
  
2. Составим множества <tex>P</tex>, <tex>S</tex>, и <tex>N</tex>:
+
* Составим множества <tex>P</tex>, <tex>S</tex>, и <tex>N</tex>:
 
:<tex>P(e')=\{a_1,b_4\}</tex>,<br />
 
:<tex>P(e')=\{a_1,b_4\}</tex>,<br />
 
:<tex>S(e')=\{a_1,b_3,a_5\}</tex>,<br />
 
:<tex>S(e')=\{a_1,b_3,a_5\}</tex>,<br />
Строка 122: Строка 139:
 
Так как пустое слово принадлежит языку, то <math>\Lambda(e')=\{\varepsilon\}</math>.
 
Так как пустое слово принадлежит языку, то <math>\Lambda(e')=\{\varepsilon\}</math>.
  
3. Автомат локального языка <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>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>1</tex> (соответствующего пустой строке) в два состояния из <tex>P'</tex>, переход из <tex>a</tex> в <tex>b</tex> если <tex>ab \in N'</tex>, три состояния <math>S'</math> терминальные (как и состояние <tex>1</tex>).  
  
4. Получим автомат для <tex>L(e)</tex> удалив индексы, добавленные на первом этапе.
+
* Получим автомат для <tex>L(e)</tex>, удалив индексы, добавленные на первом этапе.
  
 
== См. также ==
 
== См. также ==
Строка 131: Строка 148:
  
 
== Источники информации ==
 
== Источники информации ==
* Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. {{---}} М.:Издательский дом «Вильямс», 2002.
+
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' {{---}} Введение в теорию автоматов, языков и вычислений
* Mark V. Lawson Finite Automata, стр 132.
+
* ''Mark V. Lawson'' {{---}} Finite Automata
 +
* [https://en.wikipedia.org/wiki/Glushkov's_construction_algorithm Wikipedia {{---}} Glushkov's construction algorithm]
  
 
[[Категория: Теория формальных языков]]
 
[[Категория: Теория формальных языков]]
 
[[Категория: Автоматы и регулярные языки]]
 
[[Категория: Автоматы и регулярные языки]]
 +
[[Категория: Другие автоматы]]

Текущая версия на 17:47, 18 апреля 2018

Описание[править]

Определение:
Граф Майхилла [math]G[/math] (над алфавитом [math]\Sigma[/math]) (англ. Myhill graph) — ориентированный граф, удовлетворяющий свойствам:
  1. Для каждой упорядоченной пары вершин [math]v[/math] и [math]u[/math] существует только одно ребро из [math]v[/math] в [math]u[/math].
  2. Некоторые вершины обозначены начальными, а некоторые — конечными. Ребро может одновременно быть начальным и конечным.
  3. Вершины обозначены различными символами из конечного алфавита [math]\Sigma[/math], то есть мы можем обращаться к вершине по ее символу.


Пусть [math]G[/math] — граф Майхилла над алфавитом [math]\Sigma[/math].

Символ [math]c \in \Sigma[/math] назовем разрешенным, если им помечена вершина, являющая одновременно начальной и конечной.

Не пустая строка [math]c_1c_2 \ldots c_n[/math] из [math]\Sigma^*[/math] длиной не менее двух символов, называется разрешенной, если символом [math]c_1[/math] отмечена стартовая вершина, а символом [math]c_n[/math] — конечная, и для всех [math]1 \leqslant i \leqslant n - 1[/math] в [math]G[/math] существует ребро [math](c_i, c_{i+1})[/math].

Язык [math]L(G)[/math], распознаваемый графом Майхилла, состоит из всех разрешенных строк из [math]\Sigma^+[/math].

Покажем, что графы Майхилла могут быть представлены в виде автоматов. Пусть [math]\mathcal{A} = (S, \Sigma, i, \delta, T)[/math] ДКА.


Определение:
Автомат [math]\mathcal{A}[/math] называется локальным (англ. local automaton, Glushkov automaton), если для любого [math]c[/math] из [math]\Sigma[/math] множество [math]\{\delta(s, c) \mid s \in S\}[/math] содержит не более одного элемента.


Определение:
Локальный автомат [math]\mathcal{A}[/math] называется стандартным локальным автоматом (англ. standard local automation), если в нем нет перехода в начальное состояние.


Таким образом, автомат является локальным, если для каждого [math]c[/math] из [math]\Sigma[/math] нет переходов, отмеченных [math]c[/math], или если все они ведут в одно состояние.

Покажем, что граф Майхилла может быть преобразован в стандартный локальный автомат таким образом, что распознаваемый им язык не изменится.

Теорема:
Язык распознается графом Майхилла тогда и только тогда, когда он распознается стандартным локальным автоматом, стартовое состояние которого не является терминальным.
Доказательство:
[math]\triangleright[/math]

[math]\Rightarrow[/math]

Пусть [math]G[/math] — граф Майхилла.
Построим автомат [math]\mathcal{A}[/math] следующим образом:
  • Добавим вершину [math]i[/math] в [math]G[/math] с ребрами от [math]i[/math] к каждой стартовой вершине [math]G[/math]; отметим вершину [math]i[/math] как стартовое состояние.
  • Отметим конечные вершины как терминальные состояния.
  • Отметим каждое ребро результирующего ориентированного графа символом, стоящим в вершине, на которою оно указывает.
Переходы преобразуются следующим образом: Myhill1.png
По построению стартовое состояние не является терминальным.
Покажем, что полученный автомат конечен.
Ребра, выходящие из стартового состояния обозначены различными символами, потому что они указывают на вершины, которые, по свойству 3, были отмечены различными символами в исходном автомате.
Если мы рассмотрим любое другое состояние [math] s [/math], то два перехода из [math] s [/math] могут иметь одинаковые метки только в том случае, если в [math]G[/math] оба ориентированных ребра идут в одну и ту же вершину. Но этого не может быть по свойству 1.
То есть [math]\mathcal{A}[/math] ДКА. По построению он является стандартным локальным автоматом.
Теперь просто проверить, что [math]L(\mathcal{A}) = L(G) [/math].

[math] \Leftarrow [/math]

Пусть [math] \mathcal{A} = (S, \Sigma, i, \delta, T) [/math] — стандартный локальный автомат, стартовое состояние которого не является терминальным.
Построим по нему граф Майхилла следующим образом:
  • Отметим все состояния [math] \mathcal{A} [/math], кроме стартового, [math] input [/math] символами, стоящими на ребрах, входящих в эти состояния.
  • Сотрем все метки на ребрах [math] \mathcal{A} [/math].
  • Отметим все состояния [math] s [/math] как начальные вершины, если существует переход из [math] i [/math] в [math] s [/math]
  • Отметим все терминальные состояния как конечные вершины.
  • Удалим вершину [math] i [/math] и все ребра, исходящие из нее.
Назовем полученный граф [math] G [/math] — он будет графом Майхилла по построению. Легко проверить, что [math] L(G) = L(\mathcal{A}) [/math].
[math]\triangleleft[/math]

Пример[править]

Рисунок 1
Рисунок 2

Граф Майхилла, изображенный на рисунке 1 может быть использован для распознавания строк над алфавитом [math]\Sigma = \{a, b\}[/math]. По определению, язык, распознаваемый данным графом, состоит из непустых строк, начинающихся и заканчивающихся на [math]a[/math].

Недетерминированный автомат на рисунке 2 является локальным автоматом и распознает тот же самый язык.

Локальный язык[править]

Рассмотрим язык, распознаваемый стандартным локальным автоматом.

Определение:
Язык [math]L \subseteq A^*[/math] называется локальным языком (англ. local language), если [math]L \setminus \varepsilon[/math] может быть описан следующим образом:
[math]\exists P, S \subseteq A, N \subseteq A^2: L \setminus \varepsilon = (P A^* \cap A^* S) \setminus A^* N A^*[/math].


Другими словами, непустое слово принадлежит локальному языку, если оно начинается с символа из [math]P[/math], оканчивается на символ из [math]S[/math] и не содержит пары символов из множества [math]N[/math].

Пусть [math]L = (P A^* \cap A^* S) \setminus A^* N A^*[/math] — локальный язык. Определим автомат [math]\mathcal{A}[/math] следующим образом:

  • набор состояний [math]Q = A \cup \{ \varepsilon \}[/math],
  • начальное состояние [math]\varepsilon[/math],
  • терминальные состояния [math]S[/math],
  • [math]\delta(\varepsilon, a) = a[/math] если [math]a \in P[/math] и [math]\delta(a, b) = b[/math] если [math]ab \not\in N[/math].

Если [math]L[/math] содержит пустую строку, то множество терминальных состояний [math]\mathcal{A}[/math][math]S \cup \{ \varepsilon \}[/math].

Утверждение:
Определенный таким образом автомат [math]\mathcal{A}[/math] — стандартный локальный автомат, распознающий [math]L[/math].
[math]\triangleright[/math]

Автомат является локальным поскольку для каждого состояния [math]s[/math] и любого символа [math]a[/math] [math]\delta(s, a)[/math] либо неопределена либо равна [math]a[/math]. По построению автомат является стандартным. Покажем, что [math]L(\mathcal{A}) = L[/math].
Пусть [math]x = a_1 \ldots a_n \in L(\mathcal{A})[/math]. Тогда в автомате существует путь:

[math]\varepsilon \xrightarrow{a_1} a_1 \xrightarrow{a_2} a_2 \ldots a_{n-1} \xrightarrow{a_n} a_n[/math].

Здесь [math]a_n[/math] — терминальное состояние, [math]a_n \in S[/math]. Переход из [math]\varepsilon[/math] в [math]a_1[/math] определен, поэтому [math]a_1 \in P[/math]. Для каждого [math]j: 1 \leqslant j \leqslant n - 1[/math] факт, что переход [math]a_j \rightarrow a_{j+1}[/math] существует, означает что [math]a_j a_{j+1} \not \in N[/math]. Следовательно, [math]x \in L[/math].

Пусть [math]x = a_1 \ldots a_n \in L[/math]. Тогда [math]a_1 \in P[/math], [math]a_n \in S[/math] и для каждого [math]j[/math] [math]a_j a_{j+1} \not \in N[/math]. Следовательно в автомате существует путь из начального состояния в терминальное:

[math]\varepsilon \xrightarrow{a_1} a_1 \xrightarrow{a_2} a_2 \ldots a_{n-1} \xrightarrow{a_n} a_n[/math].
Следовательно, [math]x \in L(\mathcal{A})[/math].
[math]\triangleleft[/math]
Утверждение:
Язык, распознаваемый локальным автоматом, является локальным.

Алгоритм Глушкова[править]

Описание[править]

Дано регулярное выражение [math]e[/math]. Алгоритм Глушкова строит недетерминированный автомат, который распознает язык [math]L(e)[/math], распознаваемый [math]e[/math]. Построение происходит в несколько шагов:

  • Линеаризация регулярного выражения. Каждый символ из алфавита, содержащийся в регулярном выражении, переименовывается таким образом, что каждый символ содержится в новом регулярном выражении не более одного раза. Пусть [math]A[/math] — исходный алфавит, [math]B[/math] — новый алфавит.
  • Вычисление множеств [math]P(e'), S(e'), N(e')[/math], где [math]e'[/math] — линеаризованное регулярное выражение. [math]P(e')[/math] — множество символов, с которых начинается слово из [math]L(e')[/math]. [math]S(e')[/math] — множество символов, на которые оканчивается слово из [math]L(e')[/math] и [math]N(e')[/math] — множество пар символов, которые встречаются в слове из [math]L(e')[/math]. Более формально:
    [math]P(e')=\{a\in B\mid aB^*\cap L(e')\ne\emptyset\}[/math],
    [math]S(e')=\{a\in B\mid B^*a\cap L(e')\ne\emptyset\}[/math],
    [math]N(e')=\{u\in B^2\mid B^*uB^*\cap L(e')\ne\emptyset\}[/math].
  • Вычисление множества [math]\Lambda(e')[/math] такого что [math]\Lambda(e')=\{\varepsilon\}\cap L(e')[/math].
  • Вычисление локального языка с заданными множествами и построение по нему автомата.
  • Делинеаризация, переименование каждого символа из [math]B[/math] в соответствующий ему символ из [math]A[/math].

Пример работы[править]

Автомат, построенный в ходе работы алгоритма Глушкова

Рассмотрим регулярное выражение [math]e = (a(ab)^*)^* + (ba)^*[/math]:

  • Линеаризуем его путем добавления индекса к каждому символу:
[math]e'=(a_1(a_2b_3)^*)^*+(b_4a_5)^*[/math].
  • Составим множества [math]P[/math], [math]S[/math], и [math]N[/math]:
[math]P(e')=\{a_1,b_4\}[/math],
[math]S(e')=\{a_1,b_3,a_5\}[/math],
[math]N(e')=\{a_1a_2, a_1a_1, a_2b_3, b_3a_1,b_3a_2,b_4a_5,a_5b_4\}[/math].

Так как пустое слово принадлежит языку, то [math]\Lambda(e')=\{\varepsilon\}[/math].

  • Автомат локального языка [math]L'=P'B^*\cap B^*S'\setminus B^*(B^2\setminus N')B^*[/math] содержит начальное состояние, обозначенное как [math]1[/math], и состояния для каждого из пяти символов алфавита [math]B=\{a_1, a_2, b_3, b_4, a_5\}[/math].

В построенном автомате существует переход из [math]1[/math] (соответствующего пустой строке) в два состояния из [math]P'[/math], переход из [math]a[/math] в [math]b[/math] если [math]ab \in N'[/math], три состояния [math]S'[/math] терминальные (как и состояние [math]1[/math]).

  • Получим автомат для [math]L(e)[/math], удалив индексы, добавленные на первом этапе.

См. также[править]

Источники информации[править]

  • Хопкрофт Д., Мотвани Р., Ульман Д. — Введение в теорию автоматов, языков и вычислений
  • Mark V. Lawson — Finite Automata
  • Wikipedia — Glushkov's construction algorithm