Конечные автоматы
1. Введение
В настоящем реферате будут даны определения детермини-
рованных и недетерминированных конечных автоматов, приведе-
ны их графы. Далее будет рассмотрен случай преобразования
недетерминированного конечного автомата в детерминированный
с рисунками и графами.
Все рассмотренные здесь автоматы представлены как маши-
ны, распознающие цепочки символов.
2. Детерминированные конечные автоматы.
В различных источниках приводятся несколько отличающие-
ся друг от друга определения детерминированного конечного
автомата. Приведем здесь определение из источника [2].
Детерминированным конечным автоматом (ДКА) называется
машина, распознающая цепочки символов. Она имеет входную
ленту, разбитую на клетки, головку на входной ленте (вход-
ную головку) и управляющее устройство с конечным числом
состояний (рис. 1). Конечный автомат М можно представить в
виде пятерки (S, I, 1б 0, 1s0 0, F), где
1) S - множество состояний 1управляющего устройства 0,
2) I - 1входной алфавит 0(каждая клетка входной ленты со-
держит символ из I),
3) 1б 0 - отображение из S x I в S (если 1б 0( 1s 0, 1a 0) = 1s' 0, то
всякий раз, когда М находится в состоянии 1s 0, а входная
головка обозревает символ 1a 0, М сдвигает входную головку
вправо и переходит в состояние 1 s' 0),
4) 1 s0 0 - выделенное состояние в S, называемое 1начальным 0,
5) F - подмножество в S, называемое множеством 1допуска-
1ющих 0 (или 1 заключительных 0) 1 состояний 0.
┌─────┬─────┬─────┐
│ 1b 0 │ 1a 0 │ 1c 0 │ Входная лента
└─────┴─────┴─────┘
^
│ Головка
┌──┴──┐
│ 1s 0 │ Управляющее устройство
└─────┘
Рис. 1. Конечный автомат
ДКА выполняет шаги, определяемые текущим состоянием его
блока управления и входным символом, обозреваемым входной
головкой. Каждый шаг состоит из перехода в новое состояние
и сдвига входной головки на одну клетку вправо. Оказывает-
ся, что язык представим регулярным [2] выражением тогда и
только тогда, когда он допускается некоторым конечным авто-
матом.
Далее будет приведено определение ДКА через определение
недетерминированного конечного автомата (НКА), то-есть
можно будет рассматривать ДКА в качестве подмножества НДКА.
2. Недетерминированные конечные автоматы
Для каждого состояния и каждого входного символа НКА
имеет нуль или более вариантов выбора следующего шага. Он
может также выбирать, сдвигать ему входную головку при из-
менении состояния или нет.
Приведем определение недетерминированного конечного ав-
томата.
Недетерминированным конечным автоматом называется пя-
терка (S, I, 1 б 0, 1 s0 0, F), где
1) S - конечное множество состояний устройства управле-
ния;
2) I - 1 алфавит 0 входных символов;
3) 1б 0- 1функция переходов 0, отображающая S x (I U { 1e 0}) в
множество подмножеств множества S;
4) 1 s0 0 (- S - 1 начальное состояние 0 устройства управления;
5) F _( .S - множество 1заключительных (допускающих) 0сос-
тояний.
С каждым НКА связан ориентированный граф, естественным
образом представляющий функцию переходов этого автомата.
Приведем определение для графа ( или диаграммы) перехо-
дов автомата М = (S, I, 1б 0, 1s0 0, F).
Графом переходов автомата М называют ориентированный
граф G = (S, E) с помеченными ребрами. Множество ребер Е и
метки определяются следующим образом. Если 1б(s, a) 0содержит
1s' 0для некоторого 1a 0(- I U { 1e 0}, то ребро 1(s, s') 0принадле-
жит Е. Меткой ребра 1(s, s') 0служит множество тех 1b 0(- I U
{ 1e 0}, для которых 1 б(s, b) 0 содержит 1 s' 0.
Например на рис. 2. изображен граф переходов для неко-
торого НКА. Заключительное состояние обведено двойной рам-
кой.
┌─────┐
1a,b 0 │ v
│ ┌─────┐ 1a 0 ┌─────┐
└──┤ 1s1 0 ├────────────────────│ 1s2 0 │
└─────┘ ┌──────────└──┬──┘
^ │ │
│ 1e 0 │ │
└────────────┼───────┐ │ 1b
│ │ │
1e 0 │ │ │
│ │ v
┌=====┐─────────┘ └── ┌─────┐
│ 1s4 0 │────────────────────┤ 1s3 0 │
└=====┘ 1 a 0 └─────┘
Рис. 2. Пример графа переходов
Для дальнейшего рассмотрения вопроса приведения недер-
минированного конечного автомата к детерминированному, пот-
ребуется указать несколько теорем. Теоремы приведены без
доказательства, для их подробного рассмотрения предлагается
обратиться к [2].
_Теорема 1. .Всякий язык, допускаемый недерминированным
конечным автоматом регулярен.
_Теорема 2. .Пусть 2а 0 - регулярное выражение. Тогда най-
дется НКА М = (S, I, 1б 0, 1s0 0, { 1Sf 0}), допускающий язык, предс-
тавленный 2а 0, и обладающий такими свойствами:
1) ││S││
2) для каждого 1a 0 (- I U { 1e 0} множество 1 б(Sf, a) 0 пусто,
3) для каждого 1s 0(- S сумма чисел ││ 1б(s, a) 0││ по всем 1а
из I U { 1e 0} не превосходит 2.
Эти теоремы будут использованы при преобразовании НКА в
ДКА в следующем пункте.
3. Преобразование НКА в ДКА
Существует дополнительный результат или возможность со-
поставить какому-либо взятому НКА эквивалентную "детермини-
рованную" машину. Однако детерминированный конечный авто-
мат, эквивалентный данному НКА с n состояниями, может иметь
вплоть до 2 в n степени состояний. Поэтому переход от НКА к
детерминированному автомату не всегда дает эффективный спо-
соб моделирования недетерминированного конечного автомата.
Однако ДКА позволяют проще формализовать модель автомата и
алгоритмизировать его поведение. Кроме этого детерминиро-
ванные автоматы применяются при распознавании образов.
Таким образом мы можем дать определение ДКА как подмно-
жества или частного случая НКА.
Детерминированным конечным автоматом называется неде-
терминированный конечный автомат (S, I, 1б 0, 1s0 0, F), в кото-
ром:
1) 1 б(s, e) 0 = (/) (пустое множество) для всех 1 s 0 (- S,
2) ││ 1б(s, a) 0││ < = 1 для всех 1 s 0 (- S и 1 а 0 (- I.
Приведем теорему, которая поможет связать и выразить
недетерминированный конечный автомат через его детерминиро-
ванный эквивалент.
_Теорема 3. .Если L - регулярное множество, то оно допус-