Реферат: Конечные автоматы
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(- IU { 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 │
└=====┘ 1a 0 └─────┘
Рис. 2. Пример графа переходов
Для дальнейшего рассмотрения вопроса приведения недер-
минированного конечного автомата кдетерминированному, пот-
ребуется указать несколько теорем. Теоремы приведены без
доказательства, для их подробного рассмотренияпредлагается
обратиться к [2].
_Теорема 1. .Всякий язык, допускаемыйнедерминированным
конечным автоматом регулярен.
_Теорема 2. .Пусть 2а 0 — регулярное выражение. Тогда най-
дется НКА М = (S, I, 1б 0, 1s0 0, { 1Sf 0}), допускающий язык, предс-
тавленный 2а 0, и обладающий такимисвойствами:
1) ││S││ < = 2│ 2a 0│,где │ 2а 0│ — длина выражения 2 а 0,
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 — регулярноемножество, то оно допус-
кается некоторым ДКА.
Доказательство. По теореме 1 L допускается некоторым
НКА М = (S, I, 1б 0, 1s0 0, { 1Sf 0}). Превратим Мв ДКА следующим
образом. Сначала найдем такие пары состояний 1(s, t) 0, что
1(s, e) 0├─ м* 1(t, e) 0. Чтобы сделать это, построим ориентиро-
ванный граф G = (S, E), у которого 1(s, t) 0принадлежит Е
тогда и только тогда, когда 1б(s, e) 0содержит 1t 0. Затем вы-
числим рефлексивное и транзитивное замыкание G' = (S, E')
графа G. Мы утверждаем, что 1(s, e) 0├─м* 1(t, e) 0тогда и
только тогда, когда 1 (s, t) 0 принадлежитЕ'.
Теперь построим такой НКА М' = (S', I, 1б 0', 1s0 0, F), что
L(M') = L(M) и в М' нет 1 е 0- переходов.
1) 1S' = {s0} U {t│б(s, a) 0содержит 1t 0для некоторого 1s
(- S и некоторого 1а 0(-I 1} 0.
2) Для каждого 1 s 0 (- S' икаждого 1 а 0 (- I
1б'(s, a) = {u│(s, t) 0 (- E' и 1б(t, a) 0 содержит 1u} 0.
3) F' = 1 {s│(s,f) 0 (- E' и 1 f 0 (- F 1} 0.
Таким образом L(M) =L(M') и в M' нет переходов по 1 е 0.
Далее по M' построим ДКА M'', состояния которогообра-
зуют множество-степень для S'. Другими словами, M'' =
( 1P 0(S'), I, 1 б'' 0,{ 1s0 0}, F''), где
1) для каждого подмножества S множества S' икаждого 1а
(- I
1б''(S,a) = {t│б'(s, a) 0содержит 1t 0для некоторого 1s 0(-
S 1} 0,
2) F'' = {S│S П F<> (/)}.
Далее с помощью индукции по │ 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│состояниями.
Таким образом уже само построение ДКА можетвызвать
непреодолимые трудности.