XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 84
Текст из файла (страница 84)
Одним из важных теоретических следствий теоремы о детерминизации является следующая теорема. Рнс. Т.ДЕ Теорема 7.8. Дополнение регулярного ломка есть регулярный язык. 7.6. Детермввввацив вовечимх автоматов 527 < Пусть 1 — регулярный язык в алфавите У. Тогда дополнение языка Ь (как множества слов) есть язык Х = Р' '1 Ь. Согласно теореме 7.7, для регулярного языка Ъ может быть построен детерминированный конечный автомат М, допуска ющий Ь. Поскольку в детерминированном автомате из каждой вершины по каждому входному символу определен переход в точности в одну вершину, то, какова бы ни была цепочка х в алфавите т', для нее найдется единственный путь в М, начинающийся в начальном состоянии, на котором читается цепочка я.
Ясно, что цепочка х допускается автоматом М, т.е. к Е Ь(М), тогда и только тогда, когда последнее состояние указанного пути является заключительным. Отсюда следует, что цепочка х ф ЦМ) тогда и только тогда, когда последнее состояние указанного пути не заключительное. Но нам как раз и нужен конечный автомат М', который допускает цепочку х тогда и только тогда, когда ее не допускает исходный конечный автомат М. Следовательно, превращая каждое заключительное состояние М в не заключительное и наоборот, получим детерминированный автомат, допускающий дополнение языка Ь.
~ Доказанная теорема позволяет строить конечный автомат, не допускающий определенное множество цепочек, следующим методом: строим сначала автомат, допускающий данное множество цепочек, затем детерминизируем его и переходим к автомату для дополнения так, как зто указано в доказательстве теоремы 7.8. Пример 7.10. а. Построим конечный автомат, допускаюп~ий все цепочки в алфавите 10, Ц, кроме цепочки 101. Сначала построим конечный автомат, допускающий единственную цепочку 101. Этот автомат приведен на рис. 7.17. 528 7. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЗЫКИ Этот автомат квазидетермикированкьп1, но не детерминированный, так как он не полкосшью определен. Проведем его детерминизацию и получим детерминированный эквивалентный конечный автомат, изображенный на рис. 7.18.
Рис. 7.18 Рис. 7.19 И наконец, переходя к дополнению (и переименовывая состояния), получим автомат, изображенный на рис. 7.19. Обратим внимание, что в полученном автомате все вершины, кроме вершнны яз, являются заключительными. Заметим также, что переход к дополнению, о котором идет речь в доказательстве теоремы 7.8, может быть проведен только в детерминированном автомате.
Если бы мы поменяли ролями заключительные и незаключительные вершины в автомате, изображенном на рис. 7.17, то получили бы автомат, допускающий язык (Л, 1, 10), который не является — как нетрудно сообразить — множеством всех цепочек, отличных от цепочки 101. Отметим также, что конечный автомат на рис. 7.19 допускает все цепочки, содержащие вхождение цепочки 101, но не совпадающие с самой этой цепочкой. Вот, например, путь, несущий цепочку 1011: яо, лм яз, лз, Ф. б. Построим конечный автомат, допускающий все цепочки в алфавите (0,1), кроме тех, которые содержат вхоэсдекие цепочки 101. Рассмотрим язык Ь, каждая цепочка которого содержит вхождение цепочки 101. Его можно задать так: Ь = (О+ 1)" 101(0+ 1)'.
Нам нужно построить автомат для дополнения языка Ь. Т.б. Детерииаивациа иоиечиых автоматов 529 Непосредственно по регулярному выражению в этом случае легко построить конечный автомат, допускающий язык Ь (рис. 7.20). 0,1 0,1 Рис. 7.20 Затем методом „вытягивания" проведем детермннизацию. Результат детерминизацви представлен на рис. 7.21. Рис.
7.21 Для полного решения задачи осталось только на рис. 7.21 поменять ролями заключительные и не заключительные вершины (рис. 7.22). Рис. 7.22 в- Обсудим идею построения конечного автомата, допускающего те и только те цепочки в алфавите (О, 1), которые не 530 Ч.
КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЗЫКИ начинаются цепочкой 01 и не заканчиваются цепочкой 11 (т.е. не разрешаются цепочки вида 01х и цепочки вида у11, каковы бы ни были цепочки х, у 6 (О, Ц ). В этом случае дополнением языка, для которого нужно построить конечный автомат, является множество всех та ких цепочек нулей и единиц, которые начинаются цепочкой 01 или заканчиваются цепочкой 11.
Допускающий это множество цепочек автомат строится как автомат для объединения 01(0+ 1)'+ (О+ 1)'11 тем способом, который изложен при доказательстве теоремы Клини (см. теорему 7.6). ф Из свойства замкнутости класса регулярных языков относительно дополнения (см. теорему 7.8) немедленно вытекает замкнутость этого класса относительно пересечения, теоретико-множественной и симметрической разности. Следствие 7.3, Для любых двух регулярных языков Ь1 и Ьг справедливы следующие утверждения: 1) пересечение Ь1 П Ьг регулярно; 2) разность Ел '1 Ьг регулярна; 3) симметрическая разность 11ЛЬ2 регулярна. ~ Справедливость утверждений вытекает из тождеств: 1) Ь1 Пьг = Х1 0Х2, 2) Ь1 '1 Ьг = Ь1 П Ьг; 3) г1~1Ьг =(Ь10Ь2)~(Ь1ПЬг) ~ь Во-первых, полученные результаты позвоапот утверждать, что класс регулярных языков относительно операций объединения, пересечения и дополнения является булевой алгеброй, в которой единицей служит универсальный язык, а нулем— пустой язык.
Во-вторых, зти алгебраические свойства семейства регулярных языков позволяют решить важную проблему распознавания эквивалентности двух произвольных конечных автоматов. Согласно определению 7.10, конечные автоматы эквивалентны, если допускаемые ими языки совпадают. Поэтому, чтобы 531 7.7.Мвяяняэацияяояечяыя автоматов убедиться в эквивалентности автоматов М1 и Мз, достаточно доказать, что симметрическая разность языков ЦМ1) и Ь(Мз) пуста. Для этого, в свою очередь, достаточно построить автомат, допускающий эту разность, и убедиться в том, что допускаемый им язык пуст. В общем случае проблему распознавания того, что язык конечного автомата пуст, называют проблемой пустотпы длл конечного аетпомата. Чтобы решить зту проблему, достаточно найти множество заключительных состояний автомата, достижимых из начального состояния.
Так как конечный автомат — это ориентированный граф, то решить такую проблему можно, например, с помощью, поиска в ширину (см. 5.5). Язык, допускаемый конечным автоматом, пуст тогда и только тогда, когда множество заключительных состояний, достижимых из начального состояния, пусто. Практически эквивалентность конечных автоматов предпочтительнее распознавать, используя алгоритм минимизации (см.
7.7), но сейчас нам важно подчеркнуть, что принципиальная воэможность решить проблему эквивалентности вытекает из теоремы 7.7 и ее алгебраических следствий. 7.7, Минимизация конечных автоматов Может быть поставлен такой вопрос: нельзя ли для произвольного конечного авшемата построить эквивалентный конечный авпьоматп с меньшим числом сосшояний7 Оказывается, что ответ на этот вопрос положителен.
Более того, можно построить конечный автомат, эквивалентный исходному и имеющий наименьшее число состояний (среди всех конечных автоматов, эквивалентных ему). Процедуру построения такого автомата называют минимизацией конечного аетпомапмь В силу теоремы о детерминиэаиии (см. теорему 7.7) можно считать, что исходный конечный автомат М=(К Я до Р, б) является дешерминированным. 532 7. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЗЫКИ Будем также предполагать, что в исходном конечном автомате нет состояний, которые не достижимы из начального состояния.
Это предположение мотивировано тем, что если в М существуют состояния, не достижимые из начального, то их можно найти (используя, скажем, поиск в ширину на графе М) и удалить со всеми иниидентными им дугами. На множестве состояний автомата М зададим семейство отношений эквивалентности следующим образом: 1) О-эквиваленпаносепае для произвольных состояний д1 и дг полагаем д1 = дг тогда и только тогда, когда они оба явля- — О ются заключительными или оба не являются заключительными; 2) й-энвиваленпаностпь: при й > 1 полагаем д1 =~ дг тогда и только тогда, когда д1 = дг, т.е. состояния д1 и дг — а-1 (Й вЂ” 1)-эквивалентны, и, кроме того, для любого входного символа а состояния 6(дна) и 6(дг, а) также (й — 1)-эквивглентны'.
Чтобы понять смысл отношения й-эквивалентности, обратимся к рис. 7.23. На этом рисунке д1 и дг — (й-1)-эквивалентные состояния, т.е. они принадлежат одному и тому же клас- 1 Чп о су (й — 1)-эквивалентности Сь Эти состояния, согласно данному выше Че (Ч,а определению, станут Й-эквивглентс, Се ными, если для любого входного симРис. 7.23 вола а состояния 6(дна) и 6(дг,а) также являютсн (й — 1)-эквиваяентными, содержащимися в некотором классе (Й вЂ” 1)-эквивалентности Сг (возможно, что С1 = Сг). Можно сказать, что (й — 1)-эквивалентные состояния будут также и й-эквивалентными, если переход из них по любому входному символу „сохраняета (Й-1)-эквивалентность состояний, т.е. состояния, в которые конечный автомат переходит из (Й вЂ” 1)-эквивалентных состояний, снова окажутся (Й вЂ” 1)-эквивалентными.
'Напомним, что эркиакл оерелодое детерминироааиного конечного аатомата определена как отображение 6: й х У -+ О (см. замечание 7.7). 7.7. Минвмяаааив конечных автоматов 533 Если же найдется хотя бы один входной символ а, такой, что состоя- % Л(% 4 ния б(е1,а) и Б(®,а) окажутся в разных классах (Й-1)-эквивалентности Ч2 д(яв а) (рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
