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
і і і
ok
$u
Текущая страница: 1
|
