Информатика, программирование: Конечные автоматы, Реферат

Категория: Информатика, программирование
Тип: Реферат

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│ 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 содержит 1 u} 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). Приведем его из

недетерминированного вида в детерминированный аналог.

┌──────────────────────────────────────┐

│ │

│ ┌─────┐ 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 не входит в М'.

┌───────────────────────────────────┐

│ v

┌=====┐ 1 a,b 0 ┌=====┐ 1a 0 ┌=====┐

│ 1s1 0 ├───────────_│ 1s2 0 │_─────────┤ 1s4 0 │

└=====┘ └=====┘ └=====┘

│ ^

└───┘

Рис. 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 ├───────────────┘

└=====┘

^ │

└───┘

Рис. 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│ состояниями.

Таким образом уже само построение ДКА может вызвать

непреодолимые трудности.

Еще из раздела Информатика, программирование:

Это интересно

Реклама

Поиск рефератов

Еще рефераты

Афоризм

Главарь администрации.

Гороскоп

Счётчики

Соц. сеть	Объявления	Здоровье	Рецепты	Закрыть
Погода	TV программа	Курсы валют	Каталог сайтов	Рефераты
Гороскопы	Тайна имени	Именины	Праздники	Сонник
Девушка дня	Тесты ON-Line	Игры	Анекдоты	Приколы