Преобразование НКА в ДКА

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). Приведем его из

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

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

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

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