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

       недетерминированного вида в детерминированный аналог.
                                 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│ состояниями.

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

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