XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 85
Текст из файла (страница 85)
7.24), то состояния д1 и дз уже не будут Й-эквивалентными (образно говоря, они разойдутся по разным классам Й-эквивалентности, так как переход из них по некоторому символу „разрушает" (Й вЂ” 1)-эквивалентность). Таким образом, для любого Й > О отношение эквивалентности ш"+ включаетсл в отношение =", и, следовательно, любой класс (Й+ 1)-эквивалентности включается в некоторый класс Й-эквивалентности (точнее, каждый класс Й-эквивалентности или разбивается на несколько попарно непересекающихся классов (Й+ 1)-эквивалентности, или, если все его состояния остаются (Й+ 1)-эквивалентными, не изменяется). Это значит, что разбиение множества состояний на классы (Й+ 1)-эквивалентности является, не более „крупным", т.е. содержит не меньше классов эквивалентности, чем разбиение на классы Й-эквивалентности. Минимизация конечного автомата состоит в последовательном „измельчении" разбиения множества Я на классы эквивалентности до тех пор, пока не получится разбиение, которое уже нельзя измельчить (очевидно, что такое разбиение для некоторого Й < и = ]ф всегда существует).
Более строго: указанные вьппе отношения эквивалентности строятся до такого наименьшего Й, что отношение: — » совпадет с отношением ьз» ~. Это отношение и определяет самое мелкое разбиение множества состояний. Обозначим его просто нь Тогда ааиниааальный конечный автпоааатп М = (У',Я',д~,Р',б'), т.е. автомат с наименьшим числом состояний, эквивалентный исходному, определяется следующим образом: Я'=Фи, Яо=[чо], ~ =([У]:УЕ~)~ (Ча е У) (Чд е Я)б([й], а) = [Ю(д, а)], 534 7. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЗЫКИ где через [д) обозначен класс эквивалентности состояния д по отношению—: .
Можно доказать вполне строго (аналогично доказательству корректности алгоритма детерминизации в Д.7.1), что конечные автоматы М и М> эквивалентны. Резюмируем полученные результаты в виде теоремы. Теорема 7.9. Для произвольного конечного автомата может быть построен эквивалентный ему конечный автомат с наименьшим числом состояний. Вытекающий из этой теоремы алгоритм минимизации может быть описан так: 1) строим эквивалентный исходному детерминированный конечный автомат; 2) если в полученном конечном автомате остались состояния, не достижимые из начальной вершины, удаляем их (для обнаружения таких вершин может быть использован алгоритм поиска в ширину> см. 5.5); 3) к полученному конечному автомату применяем изложенный вьппе алгоритм построения разбиения множества состояний на классы эквивалентности по отношению ве и строим минимальный конечный автомат М>, как описано вьппе.
Замечание 7.11. Если детерминизация конечного автомата проводится методом „вытягивания", то все вершины в детерминированном конечном автомате будут достижимы вз начальной вершины. Кроме того, подчеркнем еще раз, что алгоритм минимизации применяется только к детерминированным конечным автоматам.
Пример 7.11. Минимизируем конечный автомат, взображенный на рис. 7.21. Введем новые обозначения для состояний автомата: Йо)=ло 1чо ч1)=лм Йо>931=33> йо>Ч1>ЧЗ) =33> (ЯО>Я3>ЧЗ) =34> ИО 931=35. 535 7Х Мвввмввацвв воцечвых автоматов Полученный автомат изображен на рис. 7.25. Рве.
7.25 Запишем разбиение множества состояний автомата для отношения аео, 180~ 81~ 82)~ 1831 841 85). Так как состояния б(82, 0) = 80 и б(82,1) = 83 не являются 0-эквивалентными состояниями, то в разбиении для 1-эквивалентности они „разойдутся" по разным классам; разбиение, определяемое отношением: — 1, будет иметь вид 180, 81) у 182) з 1831 841 85).
Далее, при переходе к 2-эквивалентности придется „развести" состояния 80 и 81. Поскольку для всех состояний из множества 183, 84, 85) конечный автомат переходит в одно из этих же состояний, то разбиение на классы 2-эквивалентности и есть искомое „мельчайшее" разбиение: 180)) (81)1 (82), 183, 84) 85). На рис. 7.26 приведен граф минимального конечного автомата. ф Заметим, что применение рассмотренной процедуры минимизации может дать два крайних случая: 1) все состояния исходного конечного автомата окажутся эквивзлентными и тогда в минимальном конечном автомате останется только одно состояние; 536 7.
НОнечные АВтОмАты и РеГУлЯРные Языки Рис. 7.26 2) итоговое разбиение будет состоять из одноэлементных классов эквивалентности — это означает, что исходный конечный автомат нельзя минимизировать, он уже минимален. Первый случай проиллюстрирован на рис. 7.27. Здесь приведено построение и минимизация конечного автомата, допускающего язык, обозначенный регулярным выражением (а'б')'. а Ь % % аЬ (а Ь ) а,Ь Ча (а+Ь) Рис. 7.27 7.7. аеииииизапиа аонечньт автоматов 537 После удаления Л-переходов получается детерминированный автомат, все состояния которого заключительные.
Значит, минвмальный автомат состоит из одной вершины и допускает язьпс (о+ Ь)'. Тем самым мы еще и доказали эквивалентность регулярных выражений (а+ Ь)' и (а'6')' (в алфавите 1а, Ь)). Алгоритм минимизации целесообразно использовать и при распознавании эквивалентности двух заданных конечных автоматов. Если мы хотим выяснить, эквивалентны ли автоматы М1 и Мт, то можно минимизировать каждый из них. Если минимальные автоматы М1 и Мз имеют множества состояний с разным числом вершин, то исходные автоматы заведомо не эквивалентны.
Можно доказать, что исходные автоматы эквивалентны тогда и только тогда, когда соответствующие им микиамьаьиые аетпоматпы М1 и Мг изоморЯны. Конечные автоматы М1 и Мз считаются изоморфными, если существует такая биекцил Ь множества состояний первого автомата на множество состояний второго, которая является нзоморфизмом данных конечных автоматов как ориентированных гра4ов (см. 5.7) и обладает дополнительно следующими свойствами: 1) если дш — начальное состояние конечного автомата М1, то Ь(дш) = дег — начальное состояние конечного автомата Мз, 2) если Р1 — подмножество заключительных состояний конечного автомата М1, то п(Р1) = Рг — подмножество заключительных состояний конечного автомата М~', 3) для любых двух состояний о и т конечного автомата М1 н любого входного символа а д -~а г тогда и только тогда, когда Ь(д) -+ Ь(т).
В общем случае проблема распознавания эквивалентности М1 и Мг сводится к проблеме распознавания изоморфизма минимальных автоматов. Для малого числа вершин (до 10) этот нзоморфизм, как правило, распознается „невооруженным глазом", но в общем случае нужны специальные алгоритмы'. 'См., например: Кристпойидсс Н. 538 7. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЗЫКИ 7.8. Лемма о разрастании для регулярных языков В теории формальных языков большое значение имеют утверждения, в которых формулируется необходимое условие принадлежности языка к тому или иному классу языков. Эти утверждения известны в литературе под названием лемм о разрастании (или лемм о „накачке").
С помощью этих лемм удается доказать, что тот или иной язык не является языком данного класса, например, не является регуллрнььн, контпекстпно~еободнььв и т.п. Доказывать подобного рода „отрицательные" утверждения гораздо труднее, чем „положительные" (что язык есть язык данного класса С), ибо в последнем случае требуется придумать любую граммашнку соответствующего класса, порождающую данный язык, а в первом нужно каким-то образом доказать, что не существует грамматики этого класса, порождающей язык. Применение лемм о разрастании состоит в следующем: доказав, что предлагаемый язык не удовлетворяет условию леммы о разрастании, мы можем быть уверены в том, что он заведомо не принадлежит соответствующему классу языков, и нам нечего и пытаться искать для него грамматику того же класса.
Мы рассмотрим подобного рода утверждения для классов регулярных, контекстно свободных и линейных языков. Начнем с леммы о разрастании для регулярных языков. Эта лемма (см. теорему 7.10) утверждает, что любой регулярный язык допускает представление всех своих достаточно длинных цепочек в виде соединения трех цепочек, причем средняя цепочка иэ этих трех не пуста, ограничена по длине, и ее „накачка" — повторение любое число раз — или выбрасывание не выводит за пределы языка (т.е. дает цепочки, принадлежащие данному регулярному языку).
Теорема 7.10. Если Ь вЂ” регулярный язык, то существует натуральная константа йс (зависящая от Ь), такая, что для 7.8. Лемма о разрастании Ляя регулярных языков 539 любой пеночки х Е Ь, д.яика которой не меньше )сь, х допускает представление в виде х = ивер, где е ~ А и )в~ < Йу„причем для любого н > 0 цепочка х„= неош Е Ь. ~ Поскольку язык Ь регулярен, то, согласно теореме Клины (см.
теорему 7.6), существует конечный автомат М = = (К Я, де, г, б), допускающий его, т.е. Ь = ЦМ) (в силу теоремы 7.7 о детерминюации можно считать М дегпврмнннрованным автоматом). Положив йь = Щ~, т.е. введя константу )сь как число состояний конечного автомата М, фиксируем проювольно цепочку х Е Ь, длина ) которой не меньше йь. Так как 1 > О, то цепочка х не является пустой, и мы можем положить х=х(1)...х(1),1>0. Поскольку конечный автомат М является детерминированным, то существует единственный путна, ведущий из начального сосвзояннл дв в одно из эаключнпьельных сосвзолниб 97, на котором читаетсл х (рис.
7.28). Рис. 7.98 Так как длина 1 цепочки х не меньше числа состояний М, т.е. числа всех вершин графа М, то, поскольку число вершин в любом пути ровно на единицу больше числа дуг в этом пути (т.е. д.анны нуепн), число вершин в рассмотренном вьппе пути будет больше, чем число всех вершин графа. Это значит, что хотя бы одна из вершин данного пути повторяетсл и она, таким образом, в силу следствия 5.1, содержится в некотором коневуре. Обозначим эту вершину через р.
Тогда нуепь, несущиб че- Ф почку х, разбивается на три части (Рис 729): 1) путьиздевр,2) кон- Чо Р ™ Ят тур, проходящий через р, 3) путь нэ р в 97. Рие. 7.99 540 7. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЗЫКИ Обозначая через и цепочку, читаемую на первой части пути, через о — цепочку, читаемую на контуре, а через ив цепочку, читаемую на третьей части, получим х = пою, причем поскольку любой контур есть вросшоб вушь, то ~о~ < Йс (длнна простого пути не может быть больше, чем число вершин графа) и о ф А, так как контур имеет ненулевую длину.
Но теперь совершенно очевидно, что контур (на котором лежит вершина р) можно пройти (по пути нз оо в Е) любое число и (при и > О) раз или ни разу. В первом случае на этом пути будет прочитана цепочка ие"ти при и > О, а во втором — и цепочка пю. Таким образом, любая цепочка х„= поою (и > О) содержится в языке Ь.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
