Локальные автоматы
Описание
Определение: |
Граф Майхилла ориентированный граф, удовлетворяющий свойствам:
| (над алфавитом ) (англ. Myhill graph) —
Пусть — граф Майхилла над алфавитом .
Символ
назовем разрешенным, если им помечена вершина, являющая одновременно начальной и конечной.Не пустая строка
из длиной не менее двух символов, называется разрешенной, если символом отмечена стартовая вершина, а символом — конечная, и для всех в существует ребро .Язык
, распознаваемый графом Майхилла, состоит из всех разрешенных строк из .Покажем, что графы Майхилла могут быть представлены в виде автоматов. Пусть ДКА.
—
Определение: |
Автомат | называется локальным (англ. local automation), если для любого из множество содержит не более одного элемента.
Определение: |
Автомат | называется стандартным локальным автоматом (англ. standard local automation), если в нем нет перехода в начальное состояние.
Таким образом, автомат является локальным, если для каждого из нет переходов, отмеченных , или если все они ведут в одно состояние.
Покажем, что граф Майхилла может быть преобразован в стандартный локальный автомат таким образом, что распознаваемый им язык не изменится.
Теорема: |
Язык распознается графом Майхилла тогда и только тогда, когда он распознается стандартным локальным автоматом, стартовое состояние которого не является терминальным. |
Доказательство: |
Пусть — граф Майхилла. Построим автомат следующим образом:
Переходы преобразуются следующим образом: По построению стартовое состояние не является терминальным. Покажем, что полученный автомат конечен. Ребра, выходящие из стартового состояния обозначены различными символами, потому что они указывают на вершины, которые, по свойству 3, были отмечены различными символами в исходном автомате. Если мы рассмотрим любое другое состояние ДКА. По построению он является стандартным локальным автоматом. Теперь просто проверить, что . , то два перехода из могут иметь одинаковые метки только в том случае, если в оба ориентированных ребра идут в одну и ту же вершину. Но этого не может быть по свойтсву 1. То есть —
Пусть — стандартный локальный автомат, стартовое состояние которого не является терминальным. Построим по нему граф Майхилла следующим образом:
|
Пример
Граф, изображенный на рисунке 1 может быть использован для распознавания строк над алфавитом
. По определению, язык, распознаваемый данным графом, состоит из непустых строк, начинающихся и заканчивающихся на .Рассмотрим детерменированный конечный автомат, представленный на рисунке 2. Не сложно проверить, что он распознает тот же язык, что и граф на рисунке 1.
Локальный язык
Рассмотрим язык, распознаваемый стандартным локальным автоматом.
Определение: |
Язык . | называется локальным языком (англ. local language), если может быть описан следующим образом:
Другими словами, непустое слово принадлежит локальному языку, если оно начинается с символа из , оканчивается на символ из и не содержит пары символов из множества .
Пусть
— локальный язык. Определим автомат следующим образом:- набор состояний ,
- начальное состояние ,
- терминальные состояния ,
- если и если .
Если
содержит пустую строку, то множество терминальных состояний — .Утверждение: |
Автомат – стандартный локальный автомат, распознающий . |
Утверждение: |
Язык, распознаваемый локальным автоматом, является локальным. |
Алгоритм Глушкова
Описание
Дано регулярное выражение
. Алгоритм Глушкова строит недетерминированный автомат, который распознает язык , распознаваемый . Построение происходит в несколько шагов:- Линеаризация регулярного выражения. Каждый символ из алфавита, содержащийся в регулярном выражении, переименовывается таким образом, что каждый символ содержится в новом регулярном выражении не более одного раза. Пусть — исходный алфавит, — новый алфавит.
- Вычисление множеств
,
,
.
, где — линеаризованное регулярное выражение. — множество символов, с которых начинается слово из . — множество символов, на которые оканчивается слово из и — множество пар символов, которые встречаются в слове из . Более формально: - Вычисление множества такого что .
- Вычисление локального языка с заданными множествами и построение по нему автомата.
- Делинеаризация, переименование каждого символа из в соответствующий ему символ из .
Пример работы
Рассмотрим регулярное выражение
.1. Линеаризуем его путем добавления индекса к каждому символу:
- .
2. Составим множества
, , и :- .
Так как пустое слово принадлежит языку, то
.3. Автомат локального языка
В построенном автомате существует переход из (соответствующего пустой строке) в два состояния из , переход из в если , три состояния терминальные (как и состояние ).
4. Получим автомат для
удалив индексы, добавленные на первом этапе.См. также
Источники информации
- Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — М.:Издательский дом «Вильямс», 2002.
- Mark V. Lawson Finite Automata, стр 132.