Локальные автоматы — различия между версиями
м (rollbackEdits.php mass rollback) |
|||
(не показаны 34 промежуточные версии 5 участников) | |||
Строка 1: | Строка 1: | ||
+ | ==Описание== | ||
+ | |||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
− | '''Граф Майхилла <tex>G</tex> (над алфавитом <tex>\Sigma</tex>)''' (англ. ''Myhill graph'') {{---}} ориентированный граф, удовлетворяющий свойствам: | + | '''Граф Майхилла <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> {{---}} граф Майхилла над алфавитом <tex>\Sigma</tex>. | Пусть <tex>G</tex> {{---}} граф Майхилла над алфавитом <tex>\Sigma</tex>. | ||
− | Символ | + | Символ <tex>c \in \Sigma</tex> назовем разрешенным, если им помечена вершина, являющая одновременно начальной и конечной. |
− | Не пустая строка <tex>c_1c_2 | + | Не пустая строка <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> называется '''локальным''' (англ. ''' | + | |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= | + | |definition=Локальный автомат <tex>\mathcal{A}</tex> называется '''стандартным локальным''' автоматом (англ. ''standard local automation''), если в нем нет перехода в начальное состояние. |
}} | }} | ||
− | Таким образом, автомат является локальным, если для каждого <tex>c</tex> из <tex>\Sigma</tex> нет переходов, отмеченных <tex>c</tex>, или если все они в одно состояние. | + | Таким образом, автомат является локальным, если для каждого <tex>c</tex> из <tex>\Sigma</tex> нет переходов, отмеченных <tex>c</tex>, или если все они ведут в одно состояние. |
Покажем, что граф Майхилла может быть преобразован в стандартный локальный автомат таким образом, что распознаваемый им язык не изменится. | Покажем, что граф Майхилла может быть преобразован в стандартный локальный автомат таким образом, что распознаваемый им язык не изменится. | ||
Строка 42: | Строка 39: | ||
<tex>\Rightarrow</tex> | <tex>\Rightarrow</tex> | ||
− | Пусть <tex>G</tex> {{---}} граф Майхилла. | + | :Пусть <tex>G</tex> {{---}} граф Майхилла. |
− | Построим автомат <tex>A</tex> следующим образом: | + | :Построим автомат <tex>\mathcal{A}</tex> следующим образом: |
− | * Добавим вершину <tex> | + | :* Добавим вершину <tex>i</tex> в <tex>G</tex> с ребрами от <tex>i</tex> к каждой стартовой вершине <tex>G</tex>; отметим вершину <tex>i</tex> как стартовое состояние. |
− | * Отметим конечные вершины как терминальные состояния. | + | :* Отметим конечные вершины как терминальные состояния. |
− | * Отметим каждое ребро результирующего ориентированного графа символом, стоящим в вершине, на которою оно указывает. | + | :* Отметим каждое ребро результирующего ориентированного графа символом, стоящим в вершине, на которою оно указывает. |
− | Переходы преобразуются следующим образом: [[Файл:Myhill1.png|150px]] | + | :Переходы преобразуются следующим образом: [[Файл: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 является локальным автоматом и распознает тот же самый язык. | |
− | |||
− | |||
− | |||
− | |||
− | <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> | ||
+ | }} | ||
+ | |||
+ | Другими словами, непустое слово принадлежит локальному языку, если оно начинается с символа из <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] | ||
+ | |||
+ | [[Категория: Теория формальных языков]] | ||
+ | [[Категория: Автоматы и регулярные языки]] | ||
+ | [[Категория: Другие автоматы]] |
Текущая версия на 19:11, 4 сентября 2022
Описание
Определение: |
Граф Майхилла ориентированный граф, удовлетворяющий свойствам:
| (над алфавитом ) (англ. Myhill graph) —
Пусть — граф Майхилла над алфавитом .
Символ
назовем разрешенным, если им помечена вершина, являющая одновременно начальной и конечной.Не пустая строка
из длиной не менее двух символов, называется разрешенной, если символом отмечена стартовая вершина, а символом — конечная, и для всех в существует ребро .Язык
, распознаваемый графом Майхилла, состоит из всех разрешенных строк из .Покажем, что графы Майхилла могут быть представлены в виде автоматов. Пусть ДКА.
—
Определение: |
Автомат | называется локальным (англ. local automaton, Glushkov automaton), если для любого из множество содержит не более одного элемента.
Определение: |
Локальный автомат | называется стандартным локальным автоматом (англ. standard local automation), если в нем нет перехода в начальное состояние.
Таким образом, автомат является локальным, если для каждого из нет переходов, отмеченных , или если все они ведут в одно состояние.
Покажем, что граф Майхилла может быть преобразован в стандартный локальный автомат таким образом, что распознаваемый им язык не изменится.
Теорема: |
Язык распознается графом Майхилла тогда и только тогда, когда он распознается стандартным локальным автоматом, стартовое состояние которого не является терминальным. |
Доказательство: |
|
Пример
Граф Майхилла, изображенный на рисунке 1 может быть использован для распознавания строк над алфавитом
. По определению, язык, распознаваемый данным графом, состоит из непустых строк, начинающихся и заканчивающихся на .Недетерминированный автомат на рисунке 2 является локальным автоматом и распознает тот же самый язык.
Локальный язык
Рассмотрим язык, распознаваемый стандартным локальным автоматом.
Определение: |
Язык | называется локальным языком (англ. local language), если может быть описан следующим образом:
Другими словами, непустое слово принадлежит локальному языку, если оно начинается с символа из , оканчивается на символ из и не содержит пары символов из множества .
Пусть
— локальный язык. Определим автомат следующим образом:- набор состояний ,
- начальное состояние ,
- терминальные состояния ,
- если и если .
Если
содержит пустую строку, то множество терминальных состояний — .Утверждение: |
Определенный таким образом автомат — стандартный локальный автомат, распознающий . |
Автомат является локальным поскольку для каждого состояния
Здесь — терминальное состояние, . Переход из в определен, поэтому . Для каждого факт, что переход существует, означает что . Следовательно, .Пусть
|
Утверждение: |
Язык, распознаваемый локальным автоматом, является локальным. |
Алгоритм Глушкова
Описание
Дано регулярное выражение
. Алгоритм Глушкова строит недетерминированный автомат, который распознает язык , распознаваемый . Построение происходит в несколько шагов:- Линеаризация регулярного выражения. Каждый символ из алфавита, содержащийся в регулярном выражении, переименовывается таким образом, что каждый символ содержится в новом регулярном выражении не более одного раза. Пусть — исходный алфавит, — новый алфавит.
- Вычисление множеств
,
,
. , где — линеаризованное регулярное выражение. — множество символов, с которых начинается слово из . — множество символов, на которые оканчивается слово из и — множество пар символов, которые встречаются в слове из . Более формально:
- Вычисление множества такого что .
- Вычисление локального языка с заданными множествами и построение по нему автомата.
- Делинеаризация, переименование каждого символа из в соответствующий ему символ из .
Пример работы
Рассмотрим регулярное выражение
:- Линеаризуем его путем добавления индекса к каждому символу:
- .
- Составим множества , , и :
- .
Так как пустое слово принадлежит языку, то
.- Автомат локального языка
В построенном автомате существует переход из
(соответствующего пустой строке) в два состояния из , переход из в если , три состояния терминальные (как и состояние ).- Получим автомат для , удалив индексы, добавленные на первом этапе.
См. также
Источники информации
- Хопкрофт Д., Мотвани Р., Ульман Д. — Введение в теорию автоматов, языков и вычислений
- Mark V. Lawson — Finite Automata
- Wikipedia — Glushkov's construction algorithm