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