1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 72
Текст из файла (страница 72)
Ограничение на число ребер, выходящих из любого узла, легко проверяется. С) Пример 9.4. Построим НКА для регулярного выражения аЬе+ -(-с, длина которого равна 5. НКА для а, Ь и с изображены на рис. 9.4, в. С помощью конструкции рис. 9.5,в построим автомат для Ь', как показано на рис. 9.6,а.
Затем с помощью конструкции рис. 9.5,б построим автомат для аЬ», как показано на рис, 9.6,а. Наконец, с помощью конструкции рис. 9.5,а построим НКА для аЬе+с. Этот автомат, имеющий 10 состояний, изображен на рис. 9.6,в. П Необходимо упомянуть один дополнительный результат. По данному НКА можно найти эквивалентную "детерминированную" машину.
Однако детерминированный конечный автомат, эквивалентный данному НКА с и состояниями, может иметь вплоть до 2" состояний. Поэтому переход к детерминированному автомату не всегда дает аффективный способ моделирования недетерминированного конечного автомата, Тем не менее детерминированные автоматы оказыва- ") На самом деле ребро из ц в зе не нужно. Вместо него можно было бы просто отождествить з~ и з,", Точно так же на рис. 9.б,а можно было бы отождествить зг и з) в одно заключительное состояние. ааа ед.
КОНВЧНЫВ АВТОМАТЫ И РВГУЛЯРНЫВ ВЫРАЖВНИЯ Ряс. 9.6. Построеяяе НКА для ЬЬ*+а (о) для Ь', (В) для аЬ', (е) для аЬЕ+в. ются полезными в распознавании образов, и сейчас мы напомним их определение. Определение. Детерминированным конечным автоматом (ДКА) называется недетерминированный конечный автомат (5, 1, 6, В„Р), в котором 1) 6(з, з) 8 для всех ВЕ5, 2) 116(з, а)««~1 для всех ВЕ5 и а~1. Теорема 9.3.
Если Š— регулярное множество, оно допускается некоторым ДКА. Д о к а з а т е л ь с т в о. По теореме 9.2 1. допускается некото. рым НКА М=(5, 1, б, з„(зе)). Превратим М в ДКА следующим обРазом. Сначала найдем такие паРы состоЯний (з, 1), что (з, В) «-м (А В). Чтобы сделать зто, построим ориентированный граф О=(5, Е), у которого (з, 1) ~ Е тогда и только тогда, когда б (з, В) содержит 1. Затем вычислим рефлексивное и транзитивное замыкание О'=(5,Е') графа О. Мы утверждаем, что (з, В) «-м (1, з) тогда и только тогда, когда (з, () принадлежит Е'. Теперь построим такой НКА М'=(5', 1, б', В„Р), что Е(М') =Е(М) и в М' нет В-переходов. 1) 5'=(зе) 0 (46 (з, а) содержит 1для некоторого з ~ 5 и некото рого а 61).
2) Для каждого зЕ5' и каждого а~1 6'(з, а) (и)(з, 1) ~Е' и 6(1, а) содержит и). заз гл, е ллгопитмы идентиеиклции Рис, 9.7. НКА М иэ примера 9.5. 3) г'=(з!(з, 1) ЕЕ' и ~ЕЕ), В качестве упражнения предлагаем доказать, что 1.(М)= ° =1,(М'). Разумеется, в М' нет переходов по е. Далее по М' построим ДКА М", состояния которого образуют множество-степень для 5'. Другими словами, М' (У(5'), 1, 6', (зс), г'"), где 1) для каждого подмножества 5 множества Я' и каждого аб1 6"(5, а)=((~6'(з, а) содержит ( для некоторого зЕ Я), 2) г"=(513 П ЕЛИ).
В качестве упражнения предлагаем доказать индукцией по Хе~, что((зс), в) «-и'- (Я, е) тогда и только тогда, когда 5=(4(з„в) «-„;, (А е)). Таким образом, 1.(М)=1.(М')=1,(М"). П Пример 9.6. Рассмотрим НКА М на рис. 9.7. Из начального состояния з, можно достичь з, и заключительное состояние з, по путям, помеченным символом е.
Поэтому для вычисления рефлексивного и транзитивного замыкания б' ориентированного графа б, о котором шла речь в доказательстве теоремы 9.3, надо добавить ребро (з„з,). Весь граф б' изображен на рис. 9.8. По М и б' построим НКА М' (рис. 9.9). Так как в узел з, входят ребра из всех узлов графа б', обьявляем все состояния в М' заключительными. Так как единст- Рис. 9.8. Гриф б'. сл. Рлспознлвлнне овилзов а Рис.
9.9. НКА М'. Рис. 9Л0. ДКА М'. венное ребро, входящее в узел з, в диаграмме для М, помечено символом е, то з, не входит в М'. При построении ДКА М" по автомату М' образуется восемь состояний. Но только четырех из ннх можно достичь из начального состояния, так что остальные четыре можно выбросить. ДКА М" изображен иа рис. 9.!О. П 9.2. РАСПОЗНАВАНИЕ ОЕРАЗОВг ЗАДАВАЕМЫХ РЕГУЛЯРНЫМИ ВЫРАЖЕНИЯМИ Изучим задачу распознавания образов, в которой дана пспочкатекст х=а,а,...а„ н регулярное выражение сл, называемое образолс. Мы хотим найти такой наименьший индекс /, что для некоторого ~' подцепочка а,а, ь ..а~ цепочки х принадлежит языку, представленному выражением и.
Вопросы такого рода часто возникают прн редактировании текстов. Многие программы для редактирования текстов разрешают пользователю задавать типы замен в цепочке-тексте. Например, пользователь может сказать, что он хочет заменить слово у какимто другим словом в куске текста х. Чтобы выполнить такую команду, программа редактирования текста должна суметь найти вхождение слова у в х. Некоторые искусные редактнрующие программы разрешают пользователю в качестве множества заменяемых цепочек указывать регулярное множество.
Например, пользователь может ГЛ, К АЛГОРИТМЫ ИДЕИТИФИКАЦИИ сказать: "Заменить 11*) в х пустой цепочкой", имея в виду, что в х следует стереть пару квадратных скобок и символы между ними. Поставленную выше задачу можно переформулировать, заменив данное регулярное выражение а выражением р=(9и, где ! — алфавит цепочки-текста.
Можно найти первое вхождение цепочки из Ь(а) в х=а,а9...а„, обнаружив кратчайший префикс цепочки л, принадлежащий языку выражения )). Эту задачу можно решить, сначала построив НКА М для распознавания множества, представленного выражением р, а затем применив алгоритм 9.1 (см. ниже) для определения последовательности множеств состояний Зь в которые может перейти НКА М после прочтения цепочки а,а,...а, при 1= 1, 2, ..., л. Как только в Зт попадает заключительное состояние, мы можем сказать, что у цепочки а,а9...ат есть такой суффиис а,а9+,...ал что а9а9+,,а> принадлежит языку, представленному выражением а, при некотором 1(1(~.
Техника нахождения 1, т. е. левого конца образа, обсуждается в упр. 9.6 — 9.8. Один из способов моделирования поведения НКА М на цепочкетеисте х — превратить М в детерминированный конечный автомат, как в теореме 9.3. Но такой путь может оказаться слишком дорогим, поскольку от регулярного выражения р можно перейти к НКА с 2$~ состояниями, а затем к ДКА с почти 29~в~ состояниями. Уже само построение ДКА может вызвать непреодолимые трудности.
Другой способ моделирования поведения НКА М на цепочке х— сначала исключить е-переходы в М и тем самым построить НКА М' без е, как это было сделано в теореме 9.3. Затем моделировать НКА М' на входной цепочке х а,а,...а„, вычислив для каждого 1, 1( к",1(п, множество состояний Зь в которые мог бы попасть М' после прочтения а,а9...аь На самом деле каждое множество 5, — это то состояние, в которое пришел бы ДКА М", построенный в доказательстве теоремы 9.3, после прочтения а,п9...аь Применяя вту технику, можно не строить автомат М', а вычислить только те его соспжния, которые появляются при обработке цепочки х. Чтобы объяснить, как найти множество Зь надо показать, как построить 8, по 39,. Легко видеть, что О б'(з, аД, 99З9 где б' — функция переходов автомата М'.
Тогда 89 — объединение вплоть до 21111 множеств, каждое из которых содержит не больше 21р1 членов. Так как при объединении надо исключить повторяющиеся члены (иначе представление множеств может стать громоздким), то очевидное моделирование автомата М' занимает 0($19) шагов на входной символ, т. е. в общей сложности 0(лф19) шагов. Как это ни удивительно, но во многих практических ситуациях гораздо эффективнее не исключать е-переходы, а работать прямо с НКА М, построенным по теореме 9.2 из регулярного выражения р.
9.9. РАСПОЗНАВАНИЕ ОБРАЗОВ 9. !О Евн! епб Рис. 9.11. Моделирование недетерминированного конечного автомата. Решающее свойство в теореме 9.2 заключалось в том, что иа графе переходов из каждого состояния автомата М выходит не более двух ребер. Это свойство позволяет показать, что на входной цепочке х= =а,а,...а алгоритм 9.1 (см. ниже) тратит на моделирование НКА, построенного из р, 0(и!р!) шагов. Алгоритм 9.1. Моделирование недетерминированного конечного автомата Вход. НКА М=(5, 1, б, з„ г) и цепочка х=а,ае...а„ из 1". Выход. Последовательность 5„ 5„ 5„ ..., 5„, где 51 — — (з~(в„а,а,...а;))-'(з, е)), О -.!(п. Метод.
Чтобы получить 5, по 51 ь сначала найдем множество состояний Т1=(1)б(з, аг) содержит 1 для некоторого в Е51 т). Затем 1. 1ог ! -О пп1!! и до Ьей!и 2. И 1=0 1Ьеп 5, — (з,) 3. е!Зе 5; О б(з, аг); ° е З1- сопппеп1 5, еше не достигло своего конечного значения. Сейчас оно соответствует множеству Тн упомянутому выше; 4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
