Введение в теорию конечных автоматов брауэр

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.

------T-----T-----¬

¦ 1b 0 ¦ 1a 0 ¦ 1c 0 ¦ Входная лента

L-----+-----+------

¦ Головка

---+--¬

¦ 1s 0 ¦ Управляющее устройство

L------

Рис. 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 ------¬

L--+ 1s1 0 +-------------------- ¦ 1s2 0 ¦

L------ ----------- L--T---

^ ¦ ¦

¦ 1e 0 ¦ ¦

L------------+-------¬ ¦ 1b

¦ ¦ ¦

1e 0 ¦ ¦ ¦

¦ ¦ v

-=====¬---------- L-- ------¬

¦ 1s4 0 ¦ --------------------+ 1s3 0 ¦

L=====- 1 a 0 L------

Рис. 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 L----T- ¦ v

---+--¬ ¦ 1 0 ^ ¦ 1e 0 -=====¬

¦ 1s1 0 +--- ¦ L--------------- ¦ 1s4 0 ¦

L--T--- ¦ L=====-

¦ ¦ ^

¦ ¦ ¦

¦ 1e 0 ¦ ¦

¦ ¦ ¦

¦ ---+--¬ 1e 0 ¦

L------------ ¦ 1s3 0 +-------------------

L------

Рис. 3. Пример недетерминированного автомата НКА М

Из начального состояния s1 можно достичь s3 и заключи-

тельное состояние s4 по путям, помеченным символом 1е 0. Поэ-

тому для вычисления рефлексивного и транзитивного замыкания

G" ориентированного графа G, о котором шла речь в доказа-

тельстве теоремы 3, надо добавить ребро (s1, s4).

Весь граф G" изображен на рис. 4. По М и G" построим

НКА М" (рис. 5). Так как в узел s4 входят ребра из всех уз-

лов графа G", то обьявляем все состояния в М" заключитель-

ными.

------¬

¦ ¦ ------¬

¦ v ¦ ¦

¦ ------¬ ---+--¬ ¦

L--+ 1s1 0 +----------¬ ¦ 1s2 0 ¦ --

L--T--- ¦ L--T---

¦ ¦ ¦

¦ L-----------------¬ ¦

v v v

------¬ ------¬

-- ¦ 1s3 0 +-------------------------- ¦ 1s4 0 +--¬

¦ L--T--- L------ ¦

¦ ¦ ^ ¦

L------ L------

Рис. 4. Граф G"

Так единственное ребро, входящее в узел s3 в диаграмме

для М, помечено символом 1 е 0, то s3 не входит в М".

------------------------------------¬

¦ v

-=====¬ 1 a,b 0 -=====¬ 1a 0 -=====¬

¦ 1s1 0 +----------- ¦ 1s2 0 ¦ ---------+ 1s4 0 ¦

L=====- L=====- L=====-

¦ ^

L----

Рис. 5. НКА М"

При построении ДКА М"" по автомату М" образуется восемь

состояний. Но только четырех из них можно достичь из на-

чального состояния, так что остальные четыре можно выбро-

сить.

Приведенный к детерминированному виду автомат М"" при-

веден на рис. 6.

Таким образом было показана возможность приведения НКА

к ДКА. При такой операции число получившихся состояний мо-

жет существенно увеличиться, некоторые из них становятся

бесполезными. Сущность приведения заключается в том, что мы

ищем обходные пути для достижения конечного состояния,

стремясь к тому, чтобы исчезла неоднозначность перехода из

состояния в состояния в зависимости от входного символа.

Эта операция порождает несущественные состояния и поэтому,

видимо, в каждом из отдельных случаев решать задачу нужно

исходя их конкретных целей.

1b 0 -=======¬ 1 b

----------------- ¦ 1{s2,s4} 0+-------------¬

¦ L=======- v

¦ ¦ ------¬

¦ ¦ 1a 0 ¦ 1(/) 0 ¦ --¬

-=====¬ ¦ L----T- ¦

¦ 1{s1} 0 ¦ ¦ ^ ¦ ¦

L=====- v ¦ L-----

¦ 1a 0 -=====¬ 1b 0 ¦ 1 a,b

L---------------- ¦ 1{s2} 0 +----------------

L=====-

^ ¦

L----

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

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

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

Введение в теорию конечных автоматов брауэр

Похожие курсовые работы