Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 22
Текст из файла (страница 22)
2.22 дьявольское состояние И и все переходы в него. Поэтому, глядя на рис. 2.22, следует иметь в виду, что у каждого состояния есть еще дополнительные переходы в состояние Я по тем входным символам, л,чя которых переход на рисунке отсутствует. Кроме того, у состояния Я есть переход в себя по любому входному символу. 0,1,...,9 0,1,,,.,9 Рис.
2.22. ДКА Р, полученный усгпранением е-переходов на рис. 2ЛВ Поскольку начальное состояние Š— это с)о„начальным состоянием 1э является ЕС(.ОБЕ(с10), т.е. множество (до, д,). В первую очередь нужно найти состояния, в которые переходят 90 и г), по различным символам из Т.; напомним, что это знаки плюс и минус, точка и цифры от 0 до 9. Как видно на рис. 2.18, по символам + и — а, никуда не переходит, в то время как до переходит в с)ь Таким образом, чтобы вычислить бо((с)„сн), н.), нужно взять в-замыкание (еп), Поскольку к-переходов, выходящих из дн нет, получаем, что бо((с)о, сп), +) = (Ч,).
Точно так же находится 4э((с)о, с)~), -) = (су,). Эти два перехода изображены одной дугой на рис. 2.22. Теперь найдем ~з((е)о, с)1), .). Как видно на рис. 2.18, по точке с(о никуда не переходит, а д, переходит в дь Поэтому нужно взять замыкание (д,).
Но состояние дз является собственным замыканием, так как г-переходов из него нет. И, наконец, в качестве примера перехода из (ао, дД по произвольной цифре найдем бо((до с)~), 9). По цифре с(в никуда не переходит, а 111 переходит сразу в сн н с(л. Так как ни одно из этих состояний не имеет выходящих к-переходов, делаем вывод, что сеэ((с)в, с)~), 9) = (дь 11л). Последнее равенство справедливо лля всех цифр. Итак, мы объяснили, как строятся дуги на рис.
2.22. Остальные переходы находятся аналогично; проверка предоставляется читателю. Поскольку с)з есть единственное допускающее состояние Е, допускающими состояниями 0 являются те его достижимые со- 95 2.5. КОНЕЧНЫЕ АВТОМАТЫ С ЭПСИЛОН-ПЕРЕХОДАМИ стояния, которые содержат о)н На рис. 2.22 эти два состояния, (ан о!о) и (дь дн дз), отмечены двойными кружками. С) Теорема 2.22. Язык Л допускается некоторым я-НКА тогда и только тогда, когда Т, допускается некоторым ДКА. Доказательство. (Достаточность) Доказательство в эту сторону просто. Допустим, !,=ЦВ) для некоторого ДКА Р.
Преобразуем Р в я-НКА Е, добавив переходы б(9, в) = !а для всех состояний й автомата Р. Чисто технически нужно также преобразовать переходы Р по входным символам к виду НКА-переходов. Например, ~э(д, а) = р нужно превратить в множество, содержащее только состояние р, т.е. бе(о), а) = (р). Таким образом, Е и Р имеют одни и те же переходы, но при этом, совершенно очевидно, Е не содержит переходов по я, выходящих из какого-либо состояния.
(Необходкность) Пусть Е = Ят Х, ба, де, Рк) — некоторый я-НКЛ. Применим описанную выше модифицированную конструкцшо подмгюжеств для построения ДКА Р=(Ро: Е, 4о, 7о, Ро). Нужно доказать, что ЦВ) = ЦЕ). Для этого покажем, что расширенные функции переходов Е и В совпадают. Формально покажем индукцией по длине н, что б с(до, и) = о о(чо н'). Базис. Если Ро) = О, то зо = ж По определению замыкания б я(о!о, я) = ЕСЬОБЕ(ао).
Кроме того, по определению начально~о состояния Р по =ЕСЬОЕЕ(ао). Наконец, нам известно, что для любо~о ДКА б (р, к) =р, каково бы ни было состояние р. Поэтому, в частности, б о(ао, я) = ЕСЬОБЕ(ао). Таким образом, доказано, что б е(ао я) = б р(о!р я). Индукция. Предположим, что и =ха, где а — последний символ цепочки зг, и что для х утверждение справедливо. Таким образом, б е(до,х) = б о(до,х). Пусть оба эти множества состояний представляют собой (рн рь ..., рь).
По определению б для я-НКЛ находим б к(9о, зо) следующим образом. !. Пусть ( )а р(ро а) есть (гь гз.. г ). 2. Тогда д г(о!о, н) = ( ) ЕСЬОЕЕ(г„.). Внимательно рассмотрев, как ДКА Р строится посредством описанной выше модифнцированной конструкции подмножеств, мы видим, что д о((рь рь ..., ро), а) построено с помощью описанных только что шагов (!) и (2).
Таким образом, значение б ойо и') те б о((р~ рь ." рь), а), совпадает с б я(9о, ж). Тем самым доказаны равенстао б я(9о, н) = б о(Чо, н) и индуктивная часть теоремы С) 96 ГЛАВА 2. КОНЕЧНЫЕ АВТОМАТЫ 2.5.6. Упражнения к разделу 2.5 2.5.1. (в) Рассмотрите следующий е-НКА и: а) найдите е-замыкание каждого из состояний; б) выпишите все цепочки, длина которых не более 3, допустимые данным ав- томатом; в) преобразуйте данный автомат в ДКА. 2.5.2. Выполните задание упражнения 2.5.1 со следующим е-НКА. 2.5.3. Постройте е-НКА, которые попускают следующие языки.
Для упрощения построений используйте, по возможности, е-переходы: а) множество всех цепочек, состоящих из нуля или нескольких символов а, после которых стоит нуль или несколько символов Ь, и вслед за ними нуль или несколько символов с; б) П) множество цепочек, состоящих либо из повторяющихся один или несколько раз фрагментов 01, либо из повторяющихся один или несколько раз фрагментов 010; в) (!) множество цепочек из 0 и 1, в которых хотя бы на одной из последних де- сяти позиций стоит 1.
Резюме + Детерминированные конечные автовазы. ДКА имеет конечное число состояний и конечное множество входных символов. Одно из состояний выделено как на- чальное, и нуль или несколько состояний являются допускающими. Функция переходов определяет, как изменяются состояния при обработке входных символов. + Диаераммы переходов. Автомат удобно представлять в виде графа, в котором вершины соответствуют состояниям, а дуги, отмеченные входными символами, РЕЗЮМЕ соответствуют переходам из состояния в состояние. Начальное состояние отмеча- ется стрелкой, а допускающие состояния выделяются двойными кружками.
в Язык автомата. Автомат допускает цепочки. Цепочка является допустимой, если, стартуя в начальном состоянии и обрабатывая символы этой цепочки по одному, автомат переходит в некоторое допускающее состояние. В терминах диаграмм переходов цепочка является допустимой, если она состоит из символов, отме- чающих путь из начального состояния в одно из допускающих. е Оедетермииированиый конечный аетомапь НКА отличается от ДКА тем, что НКА может иметь любое число переходов (в том числе, ни одного) нз данного со- стояния в по данному входному символу.
+ Конструкция подмножеств. Множества состояний НКА можно рассматривать как состояния некоторого ДКА. Таким образом, мы можем преобразовать НКА в ДКА, допускающий тот же самый язык. е е-переходы. Можно расширить понятие НКА, разрешив переходы по пустой цепочке, т.е. вообще без входных символов. Расширенные таким образом НКА могут быть преобразованы в ДКА, допускающие те же самые языки. + Приложения типа "поиск е тексте". Недетерминнрованнью конечные автоматы представляют собой удобный способ моделирования программы поиска одного или нескольких ключевых слов в больших массивах текста. Эти автоматы либо непосредственно имитируются с помощью программы, либо вначале преобразу- ются в ДКА, а затем уже реализуются в виде программы.
Литература Принято считать, что начало формальному изучению систем с конечным числом состояний было положено в работе [2]. Однако эта работа была посвящена не теперешним ДКА, а так называемой вычислительной модели "нейронных сетей'*. ДКА, в общепринятом смысле слова, были введены независимо в нескольких различных вариантах в работах [1], [3] и [4]. Материал по недетерминированным автоматам и конструкции подмножеств взят из работы [5].
1. О. А. Ни%пап, "ТЛе зупйеяз о( зейцепйа! ззг!гсй!пй с!гсц!гз", .У««апА!!и Ьи!. 257:3 — 4 (1954), рр. 161-190 апд 275-303. 2. Ч/. 5. МсСцйосй апд Ч!. Р!пз, "А 1оя!са!са1сп1ов о(йе !деаз 'пппзапепс !и пегчпоца аспчйу", Ви!!. Май. В!арбуз!сз 5 (1943), рр. 1! 5 — 133. (Маккалок У.С., Питтс Э. Логическое исчисление идей, относящихся к нервной активности.
! сб. "Аетоматы".— Мз ИЛ, 1956. — С. 362-384.) 3. С. Н. Меа]у, "А шейод [ог зупйеяьдпй зег[цепг!а] с|гсш1з", ВеП Вузгет Тесйп!са! ./ои«па! 34:5 (1955), рр. 1045 — 1079. 98 ГЛАВА 2. КОНЕЧНЫЕ АВТОМАТЫ 4. Е.Р.Мооге, "Оебап)гоп ехрепшепгз оп зецпепг)а1 шасЫпез", 1п (6], рр.129 — 153. (Мур Э.Ф. Умозрительные эксперименты с последовательностными машинами.
/ сб. "Автоматы". — Мл ИЛ, 1956. — С. 179-210.) 5. М. О. КаЫп апг) О. $соп, '"Р)п]ге ап1оша1а апг) 1Ье]г бес)з]оп ргоЫешз", /ВЛ/./. Яезеагс/з апс/ Рече/ортепг 3:2 (1959), рр. 115-125. (Рабин М.О., Скотт Д. Конечные автоматы и задачи их разрешения. — Кибернетический сборник, вы. 4. — Мл ИЛ, 1962.— С. 56-71,) 6. С. Е. БЬаппоп апг) 1. МсСаггЬу, Аи/атаги В/иаЧев, Рппсесоп 1)ппп Ргезз, 1956. (Шен- нон К.Э., Мак-Карти Дж.
Теория автоматов. / сб. "Автоматы". — Мз ИЛ, 1956.) ЛИТЕРАТУРА ГЛАВА 3 Регулярные выражения и язьпси В этой главе вводится система записи "регулярных выражений". Такие выражения представляют собой еше один способ определения языков, рассмотренный вкратце в разделе 1.1.2. Регулярные выражения можно рассматривать также как "язык программирования" для описания некоторых важных приложений, например, программ текстового поиска или компонентов компилятора. Регулярные выражения тесно связаны с НКА и могут служить удобной альтернативой для описания программных компонентов. Определив регулярные выражения, покажем, что они могут задавать регулярные, и только регулярные, языки.
Обсудим также, каким образом регулярные выражения используются в различных системах программного обеспечения. Затем исследуем алгебраические законы для регулярных выражений. Эти законы во многом подобны алгебраическим законам арифметики, однако между алгебрами регулярных и арифметических выражений есть и существенные различия. 3.1. Регулярные выражения Перейдем от "машинного" задания языков с помощью ДКА и НКА к алгебраическому описанию языков с помощью регулярных выражений. Установим, что регулярные выражения определяют точно те же языки, что и различные типы автоматов, а именно, регулярные языки.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
