Реферат: Детерминированные и недетерминированные конечные автоматы

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 состояниями. Таким образом
уже само построение ДКА может вызвать непреодолимые трудности.