Детерминированные и недетерминированные конечные автоматы
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 (/)}. Далее с помощью индукции
по 1w 0, можно доказать, что ( 1{s0}, w) 0 м*''(S, 1e 0) тогда и
только тогда, когда S = 1{t(s0, w) 0 м*' 1(t, e)} 0. Следовательно L(M) =
L(M') = L(M''). Что и требовалось доказать. 4. Пример преобразования НКА в ДКА
На основе приведенного выше доказательства, рассмотрим пример для произвольного
НКА М (рис. 3). Приведем его из недетерминированного вида в детерминированный
аналог. 1b 1a 0
1s2 0 1a 0 v 1 0 ^ 1e 0
===== 1s1 0 1s4 0 ===== ^
1e 0 1e 0 1s3 0
Рис. 3. Пример недетерминированного автомата НКА М Из начального
состояния s1 можно достичь s3 и заключи- тельное состояние s4 по путям,
помеченным символом 1е 0. Поэ- тому для вычисления рефлексивного и транзитивного
замыкания G' ориентированного графа G, о котором шла речь в доказа- тельстве
теоремы 3, надо добавить ребро (s1, s4). Весь граф G' изображен на рис. 4. По
М и G' построим НКА М' (рис. 5). Так как в узел s4 входят ребра из всех уз- лов
графа G', то обьявляем все состояния в М' заключитель- ными.
v 1s1 0 1s2 0
v v v
1s3 0 1s4 0
^ Рис. 4. Граф G' Так единственное ребро, входящее в узел s3 в
диаграмме для М, помечено символом 1 е 0, то s3 не входит в М'. 1b
v ===== 1 a,b 0 ===== 1a 0 ===== 1s1 0
1s2 0 1s4 0 ===== ===== ===== ^
1a Рис. 5. НКА М' При построении ДКА М'' по автомату М' образуется восемь состояний.
Но только четырех из них можно достичь из на- чального состояния, так что
остальные четыре можно выбро- сить. Приведенный к детерминированному виду автомат
М'' при- веден на рис. 6. Таким образом было показана возможность приведения
НКА к ДКА. При такой операции число получившихся состояний мо- жет существенно
увеличиться, некоторые из них становятся бесполезными. Сущность приведения заключается
в том, что мы ищем обходные пути для достижения конечного состояния,
стремясь к тому, чтобы исчезла неоднозначность перехода из состояния в состояния
в зависимости от входного символа. Эта операция порождает несущественные состояния
и поэтому, видимо, в каждом из отдельных случаев решать задачу нужно исходя
их конкретных целей. 1b 0 ======= 1 b 1{s2,s4} 0
======= v 1a 0 1(/) 0 =====
1{s1} 0 ^ ===== v 1a 0 ===== 1b 0 1 a,b 1{s2} 0
===== ^ 1b Рис. 6. ДКА G''
Для примера оценки стоимости преобразования НКА в ДКА рассмотрим задачу распознавания
образов, в которой дана це- почка-текст x = a1 a2 ... an и регулярное выражение
2а 0, на- зываемое образом. Мы хотим найти такой наименьший индекс j,
что для некоторого i подцепочка ai ai+1 ... aj цепочки x принадлежит языку, представленному
выражением 2 а 0. Вопросы такого рода часто возникают при редактировании
текстов. Многие программы для редактирования текстов разре- шают пользователю
задавать типы замен в цепочке-тексте. Например пользователь может сказать,
что он хочет заменить слово y каким-то другим словом в куске текста х. Чтобы
вы- полнить такую операцию, программа редактирования текста должна суметь найти
вхождение слова у в текст х. Некоторые мощные редактирующие программы позволяют
пользователю в ка- честве множества заменяемых цепочек указывать регулярное
множество. Например пользователь может сказать: "Заменить [I*] в х пустой цепочкой",
имея в виду, что в х следует стереть пару квадратных скобок и символы между
ними. Поставленную выше задачу можно переформулировать, заме- нив данное регулярное
выражение 2а 0выражение 2b 0= I* 2a 0, где I - алфавит цепочки-текста.
Можно найти первое вхождение це- почки из L( 2a 0) в х = а1 а2 ... аn, обнаружив
кратчайший пре- фикс цепочки х, принадлежащий языку выражения 2b 0. Эту задачу
можно решить, построив НКА М для распознавания множества, представленного
выражением 2b 0, а затем определить множество состояний в которые может перейти
НКА М при прочтении це- почки а1 а2 ... аn. Один из способов моделирования поведения
НКА М на це- почке-тексте х - превратить М в детерминированный конечный
автомат, используя теорему 3. Однако такой путь окажется достаточно дорогостоящим,
поскольку от регулярного выраже- ния 2b 0можно перейти к НКА с 2 2b 0
состояниями, а затем к ДКА с почти 2 в степени 2 2b 0 состояниями. Таким образом
уже само построение ДКА может вызвать непреодолимые трудности.