1626435695-d1df5d2e6d953ce7ad4b4ccb5f4f4e30 (844296), страница 28
Текст из файла (страница 28)
В качестве начальной разметки возьмем р (е] = г, для входов г фрагмента С и рг (е) = 1 для остальных дуг. Здесь для входа е с результатами (хп..., х„) через г, обозначена сеть, содержащая ровно я вершин оп..., о, каждая нз которых содержит ровно один злемент е; ~= оо причем Ч',, (е~) = х, (1 «~1««и). Тогда непосредетвеыыым следствием теоремы 2.4 и лемм 6.6, 6.3 будет следующая Т е о р е м а 6.2. Дла стог(искоркой рааиетки р сЯормулироеанной задачи глобального анализа и длк всех дуг е уграгмента С 1втаг (С, е) = азгег$ (р (е)). На рис.
6.6 схема Югл изображена вместе с ее стационарной разметкой. в 3. Алгоритм распознавания логкыо-термальыой эквивалентности 3.1. Система вквнвалевтных преебразовапий Х . Здесь мы описываем ехеггы нрагил ЛТ1 — ЛТЗ, порождающие множество правил преобразования, которое мы обозначаем Х ЛТг (Удаление недоетигеиггих]. Фрагмент без входов равносилен пустому фрагменту.
ЛТ2 (Стягивание туликог). Фрагмеыт без выходов и без заключительных операто. ров, с номерами входов а,..., а„, равносилен фрагменту аг ак ЛТЗ (Склеигание коний, или кенироеание). Пусть фиксировано разбиение множества вервшк фрагмента С ' на ыепустые н непересекающиесы классы К, ..., К„такие, что 1) каждый класс содержит графически совпадаю|цие операторы; 2) если ыекоторая выходная дуга вершины класса К, ведет к вершине класса Кг, то соответствующие выходные дуги всех других вершки класса К~ также ведут к вершниам класса Кг., 3) если некоторая выходная дуга вершины класса К~ является выходом фрагмента С с номером Ь, то соответствухкцие выходные дуги всех других вершин класса К, — также выходьг фрагмеыта С с номером Ь.
Пусть, далев, фрагмент С' может быть получен ыз С следующим образом: из каждого класса К, (~ == 1, ..., к) берется ровно по одной вершине ио н дуга от кое либо проводится к вершине ог 123 (когда для этой дуги выполнено условие 2), либо объявляется выходом фрагмента 6' с номером Ь (когда для нее выполнено условие 3). Если в 6 имеется вход с номером а, ведущий к вершине класса Х„, то к 6' добавляется вкод с номером а, который напрев. ляется к вер1пнне о,. При перечисленных условиях 6 + 6'. ЛТ4 ~Замена переменных). Пусть переменные х к у фрагмента С ие эацеплены, причем нв одно из вхождении переменной х в компоненту связности Г информационного графа фрагмента 6 — не результат входа н не аргумент выхода.
Тогда С 6', где С' — фрагмент, получающийся из фрагмента 6 заменой всех вхождений переменной х в компоненту Г на переменную у. ЛТ5 (Удаление неиспользуемых преобразователей). Пусть (оф=, — такое подмножество преобразователей фрагмента 6, что () к вершине о„ ведет ровно одна дуга (4 =- $, ..., п); 2) вершина и~ не влияет ни на един из выходов фрагмента 6, з также вн на одну из вершин, отличных от оз, ..., о„ (4 = ::-- т,..., п). Пусть, дачее, правильный фрагмент 6' получается из фрагмента 6 заменой каждого преобразователя и, (4 = 1,..., п) на дугу Тогда 6 С'. ЛТб (Удаление неиспользуемого результата охода). Если результат х входа е фрагмента 6 не влияет нз его зерпшны я выходы, то 6 6', где фрагмент 6' получается из С исключением переменной х иа ьпюжества результатов входа е. ЛТ7 (Удаление емрогсдепной пересклки).
Если х~ Р, то м а Ь ЛТВ (Замена термог). 434 Нусзь инварианты всех дуг, ведущих к вершине о во фраз менте б, содержат равенство т = т. Тогда б С', где Г получается иа 6 аамекой аргумента и вершины и па терм т.
На рис. 6.7 приведены примеры применения каждой иа схем праввл ЛТ$ — ЛТ8. лтт -е- [ пустей еретаеат) 1 х е — ю к: г .г: г в з лтт лт+ Е х яз ят яз лтв з я и, !4~ и1 и г:-и " ге"й 4-' гз " гр"Йз лтв т,/ гззгф лтв Рис. 6.2. Првмерц прамеяеявя схем правил ЛТФ вЂ” ЛТВ хл« Теорема 6.3. Если С» С», то С»~С». Д о к а з з т е л ь с т в о.
Лт-зививзлентность фрагментов тех пар, которые составляют правила системы Х, проверяется непосредственно. Например, всякое прамененне схем правил ЛТ$— АТЗ оставляет неизменным множество всех конечных цепочек операторов фрагмента. Применение схем правил ЛТ4 — ЛТ8 хо. тя и может изменять цепочки операторов фрагмента, ио оставляет неизменной логика-термальную историю любой конечной цепочки в схеме.
( ) 3.2. Приведение и согласование фрагментов. Фрагмент 6 на зывается пригеденнмм, если для него выполнены следующие условия. (В») Каждан вершина фрагмента С лежит хотя бы иа одном пути, начинающемся входом фрагмента 6. (В2) От каждой вершины фрагмента С (кроме операторов пег ли) имеется хотя бы один путь к выходу нз С или к ааключнтельному оператору. (ВЗ) К каждому преобразователю, заключительному опера тору и оператору петли ведет ровно одна дуга фрагмента 6.
(В4) В качестве фуницнональных подтермов в тестах н за. ключительных операторах фрагмента С используются только переменные. Л е м м а 6.7. »7риз»ененигм схем яра«ил ЛТ» — ЛТЗ, АТ5, ЛТ8 еслкий фрагмент мохно преобразовать е приееденнмй. Д о к а з а т е л ь с т в о. Вершвны, недостижимые от входов фрагмента, можно удалить примеяением АТ1. После етого применением ЛТ2 можно добиться п выполнения условия В2. Заметим здесь, что нахождение вершин, недостижимых от входов, а также вершин, от которых вег пути к выходам вли заключительным операторам, можно реализовать с помощью соответствующих алгоритмов рааметкв.
Условие ВЗ достигается повторным применением ЛТЗ в сторону «копирования», кав в примере на рис. 6.7, е. Такой процесс закончатся благодаря тому, что при условии В2 во фрагменте С нет пиклических путей, проходящих только через преобразователи. Наконец, условие В4 достигается применением ЛТ5 и ЛТ8, как зто показано ка рпс. 6.7, д для случая распознавателя. ~~ Дингйним учаегпком (коротко: лучом) называется всякий приведенный фрагмент без распознавателей и ровно с одним входом. Выгодным лучом приведенного фрагмента С нааызается вхождение в С всякого максимального луча.
кончающегося выходом фрагмента 6. Со всяким приведенным фрагментом С свяжем его логический граф (коротко: л-граф) И' (С), который почучается нз 6 следую- щвм образом: каждый преобразователь а — «~ и 1 — г Ь гамемя- !26 ется фрагментом-дугой а ~ Ь, после чего «стираются» аргументы вершин н выходов, а также результаты входов. На рис. 6.8 изображены фрагменты Се н его л-граф. 1 Ю(лея Рас, 6.6. Фрегиезт Се.я я его л-треф С каждой конечной цепочкой и в л-графе (т. е. путем от входа в выходу нли заключительной вершине) свяжем слово, которое ' получается последовательным выписыванием номеров свободных : дуг, а также скмволов, приписанных вершинам цепочкк ю.
При этом предивлтный символ берется со знаком б (А <Б (О, Ц), если ! путь продолжается по й-дуге некоторого распознавателя. Мне!; жество слов, построенных таким образом по всем конечным це,' почкам л-графа, называется заикав этого л-графа. Два л-графа ' называются аежокаэяяо-яяеиаиеюияяьии, если их языки совпа,:, дают. Два приведенных фрагмента называются яедобяяьэи, если !: их л-графы автоматно-эквивалентны. Пример двух автоматио-эквивалентных л-графов изображен ; на рис 6.9. Из приведенных определений следует, что всикие лт-эивиза! леитные фрагменты являются подобными.
Отношение подобия ;:: схем в точности соответствует 1 1 ~ эквивалентности одноленточнмх ! односторонних автоматов, для: которой известны эффективные ' Р Р алгоритмы раснознававия. Ни' же мы описываем алгоритм рас- . 1 0 ; познавания подобия фрагмен: тов, основанный на алгоритме Верде распознавания эквива- 17 Ч ' лентиостн дзухленточных авто- 1 0 1 0 1 0 ; матов (см.
гл. 3). Определим для этого опера- 2 3 2 3 2 е цню ""л д ух ерш Р бе П Рис. 6.6. Пример лэуя езтеиетзеия и ия некоторого раамечен- ",„" „„ф ного графа: мы говорим, что операция склеивания удается, если выполнено следующее Уел ов и е 6Л: вершинам и и оя приписан одни и тот же символ (стоп, петля или предииатный символ), всякие однотипные 127 дуги (т.
е. 0-дуги или 1-дуги), выходящие иэ вершин о и о, являются одновременно либо внутренними, либо выходными и имеют одинаковые номера. Результатом склеивания вершин ог и ое в этом случае объявляется граф, которыи получается из исходного заменой вершин и н и одной новой вершиной о.
Этой вершине и приписывается тот же свмвол, который был приписан вершинам о и о . К о присоединяются все дуги, которые вели к о вли е или выходилв иэ пнх. Если за счет этого появляется кесколько однотипных дуг, которые ведут от о к одной в той же вершине о' или являются выходами графа, то онн отождествляются. Если же условие (6Л) ложно, то мы говорим, что операция склеиванвя не удается, а ее результат ие определен. Опишем теперь алгоритм распознавания автоматной эквивалентности двух л-графов Нт и Не. 1. Если в одном иэ л-графов имеется висячая дуга с номером входа а и с номером выхода Ь, а в другом л-графе вет висячей дуги с этими же номерами, то л-графы Н и Н объявляются автоматио пеэквивалентными и алгоритм заканчивается.
В противном случае удалим все висячие дуги в л-графах Нг и Не. 2. Склеим попарно те вершины л-графов Н и Н„к которым ведут входы этих л-графов с одинаковыми номерами. 3. Будем повторять операцию склеивания вершин о1 и оз, пока выполнено следующее У с л о в и е 6.2: существуют вершины вн ое, о(о~ чь оз) такие. что из и выходят две однотипные дуги, одна из которых ведет и ввршяне о~, а другая к вершяне оз.
При выполнении каждого склеивания будем аапоминать, какие вершины исходных л-графов склеиваются в новой вершине. Поскольку каждое склеивание умеиынает количество верпшв в графе, описанный процесс завершится после не более чем т + и склеиваний (т и н — количества вершин в исходных л-графах) либо нз-за лткиости условия (6.2), либо из-за того, что не удается одна из операций склеивания.
Т е о р е и а 6.4 (М. Берд). Если одна ие операций склеиаь ния е описанном алгоритме не удается, то Нг и Н, аетоматно иеэвеияьитаяни. Если же есе олерации свлеиеанил удаются и алеориоьи еаеершаетеа ие-еа лоасности услоеия (6.2), то Нг и Нз аетомат но-еяеиеалентни. Пара пряведвншех фрагментов Сп бз называется соеласоеан. ной, если для нев выполнены следующие условия. (С1) Множества результатов входов с одинаковыми номерами совпадают.
(С2) Всякяй выходной луч в С1 н б, завершается так назыааеммм выходным вектором пересылок, т. е. лучом Уе -ию- где (к,..., л„) — множество всех аргументов выходе с номером 1, и 1зл (1 а..г(п) у~ ф (т„ (СЗ) Если некоторая переменная л встречается в каждом из фрагментов нары, то преобразователи с результатом л имеются только внутри выходных векторов пересылок этих фрагментов. (С4) Логические графы фрагментов Сл в С, совпадают. Т е о р е м а 6-5. Прилвнвниак правил из Хлл всякую пару ят-зквиваягнзанмл у1раглснтов зюзсно преобразовать в согласованную пару.
Д о к а з а т е л ь с т в о будет состоять в построении со° хлт ° хлт гласованвой пары Сз. Сл, Сл в-~- Сз, С, в-~. Сл„по заданным лт-эквивалентным фрагментам См Сл. Первый шаг состоит в приведении фрагментов С н С„как зто делается в доказательстве леммы 6.7. Пусть, далее, Вз~ — множество результатов входа с номером 7 во фрагменте С, (1 = 1, 2). Если В~чь Вль то применением ЛТ6 добавим к множеству результатов входа с номером ) во фрагменте С, каждую переменную из В"; '~, В~ (1 а.. з, к л 2, з' Ф й). Благодаря правильности фрагментов Сл н С, добавляемые результаты входов не могут влиять нл вершины фрагментов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
