1626435695-d1df5d2e6d953ce7ad4b4ccb5f4f4e30 (844296), страница 32
Текст из файла (страница 32)
з(ы увиден сейчас, что совсем иначе обстоит дело с обобщенными инвариантами дуг. Действительно, если бы мы умели эффективно строить обобщвппыв япвариапты дуг в любых фрагментах, то тем самым мы решили бы и проблему достижимости вершин в стандартных схемах (существуег ли интерпретация, при которой вычисление проходят через выделенную вершину). Однако схема непуста тогда и только тогда, когда достижимым является хотя бы один иа ее заключительных операторов, т. е. проблему пустоты можно свести к проблеме достшкимости вершин. Таким образом, проблема нахождения обобщенных пнвариантов дуг в стандартных схемах является алгорнтмическп неразрешимой. Тем не менее, ниже мы опишем алгоритм равметки, с помощью которого можно строить подмножества инзариаптов дуг. $45 Такой алгоритм окажется достаточным для освобождения сквозных схем, т.
е. для преобразования произвольной сквозной схемы в эквивалентную свободную схему. Обобщим поыятие сети, введенное а п. 2.1 предыдущей главы. Обобщенная сеть г = ($», Ч', Г) отличается от (простой) сети только тем, что кроме прежних вершин функцыонального типа она может содержать также конечное число герихин нового логического типа. Каждая вершина логического тапа также содержит конечное число алемеытов, среди которых мы рааличаем а) предикатнме элементы с, для которых Ч' (с) ~= Я; из них выходит ровно Н (Ч' (с)] пронумерованных дуг к вершинам функционального типа; б) элементы с, соответствующие логическнм константам 1 и О, Ч' (с) ~=, :(О, 1); из них не выходит ни одной дуги (мы предполагаем ниже (О, 1) П (У Ц У) = О, с)(О) = И(1) = О)„ Как и раныпе, требуется, чтобы в обобщенной сети не было контуров и элементов-дублей, т.
е. таких различных алемеытов сх и сг, для которых Ч'(сх) = Ч" (с,) сх УХ (1 ~(1~ И(Ч» (с,))) Г (сю х) = Г (с„б). Отсюда следует, в частности, что в обобщенной сети не может быть более двух элементов, соответствующих логическим констанхам. Кроме того, мы потребуем, чтобы всякая вершина логического типа содержала не более одного алемеыта, соответствующего логической константе. Отметим, что в обобщенной сети нет дуг, ведущих к вершинам логического типа Примеры обобщенных сетей приведены на рис. 7.8.
Рт. 7.8. Обобщенные сети г1 н г2 Все ыонятия, введенные в предыдущей главе для сетей, естественным обрааом переносятся и на обобщенные сети. Мы сделаем это систематически, сохраняя старые обозначения. (Ь), если Ч»(с) = Ь, ЬЕ= р ( / У () (О, 1), И(Ь) = О, )слон (с) = (1(тх,..., т„) ~ Ю(1 ~(гс,,п) т;б=)слоге(Г(с, 1))), если Ч'(с) =1, ГЕ=Я'()У, И(/) =н)О.
146 Говорят, что вершина о обобщенной сети знает множество термов )гном (о) = () )гпоч (с). Обобщенная сеть е = ($', Ч', Г) сыь представляет множество утвержденвй азэег$ (е) = ( ) (х = еыг, = т( (х ~ Ю () (О, 1)) дг (х, т ~:= )спок, (о))). Каждая из прнведенных на рис. 7.8 обобщенных сетей г$, в2 представляет множество утвержденнй (1 = р (у (у), х), $ = р (у (у), / (у)), х = =/(у), 1=1, х=х, у=у). Забытые вершиаы сети, т. е.
вершины, не знающие ннкакнх гермов ()сном (о) = Я), можно удалять, как и раньше, начиная от вершин беэ элементов. Ясно, что такое удаление оставляет множество аззегФ (е) неизменным. Вершина о обобщенной сети в называется доступной, если в е имеется путь к о от некоторой вершины о' с элементом с', для которого Ч' (с') Е= .т', () (О, Ц. Остальные вершины называются недоступными. Как и раныпе, все недоступные вершины можно удалить, начнная с вершки о, к которым не ведет ни одной дуги к для всех элементов с которых выполнено Ч'(с] ф Ю Ц (О, т). Такое удаление снова оставляет неизменным множество утверждений, представляемое обобщенной сетью. Обобщенная сеть называется приведенной, если в ней нет нн забытых, нн недоступных вершкн.
Л е и и а 7.2. По всякой обобщенной сети в можно эффективно построить приведенную обобщенную сеть гей (е), дяя которой аээегФ ( гег( (е)) = аэзег$ (е). Д о к а э а т е льет в о аналогично доказательствулеммыбЛ. Заметим, что геб (е() = в2 для обобщенных сетей е(, е2 на рис. 7.8. Д Операция пересечения /~, для обобщенных сетей определяется в точности так же, как пересечение простых сетей. Поэтому нет ничего удивительного в том, что для обобщенных сетей справедливымн оказываются утверждения, сформулированные в леммах 6.2, 6.3 н 6.4 для простых сетей. Их доказательства мало чем отличаются от приведенных в гл. 6. Частичный порядок «~ для приведенных обобщенных сетей определяется, как н раныпе, соотношением ~«~ 2<=~ (Лв2= Ч.
Т е о р е м а 7.4. Множество приведенных обобщенных сетей вместе с операиией пересечения образует оераниченную тимурешетку. Д о к а з а т е л ь от в о получается аналогично доказательству теоремы 6Л. Ц Множество л' приведенных обобщенных сетей мы дополняем, как н раньше, элементом 1 (т'в ЕБ .'ь" в /~, 1 = 1 /~ е = в) и получаем полурешетку (М', Я, удовлетворяющую условию обрыва цепей.
447 Определение преобразователя (х:= т) для обобщенных сетей, называемого по-прежнему эффектом присваивания, ничем не отличается от приведенного в гл. 6 определения эффекта присваивания для простых сетей. Лемма 7.3. Ухе=Я УтеБ Т Уг„геях"' <х -'= т> (' Л ') = ((х:= т> гв) Л (<х -= т> в ). Л е им а 7.4. Пусть ге= 2' и йеп (б, и) = аввегь (г) длн пути и ео фрагменте б. Тогда яеп (6, иАе) = амюгь ((х:= т) г), еде А — оператор присваивания х:= — т, а е — емходкщае из него дуга. Леммы 7.3 и 7.4 означают дистрибутивность эффекта присваввания и его содержательную корректность. Доказательство этих лемм можно получить повторением докаэательств лемм 6.5 и 6.6 соответственно. Двухместную операцию ай1, определенную в и.
2.3 предыдущей главы, можно применять и к обобщенным сетям. Если з в=- 6= М', а т — функциональныи терм, логическое выражение или т = Ь, где Ь ~ (О, 1), то применение этой операции дает обобщенную сеть айй (в, т), в которой есть элемент, знающий т. Введем, наконец, еще один преобразователь обобщенных сетей, называемый эффектом теста л с результатом Ь, (Ь = л): М' -ь М', где Ь Е= (О, 1), а л — логическое выражение. Этот преобразователь произвольную обобщенную сеть г е= М' преобразует в приведенную обобщенную сеть з' = (Ь = л) г следующим образом.
Если з = 1, то г' = 1. Если же г чь 1, то пусть з1 = = ааа (аой (г, Ь), л), а обобщенная сеть з2 получается иэ в1 объединением вершин о и о, акающих Ь и л соотве~ственно. Более точно, вершины о и ив заменяются одной новой вершиной, в которую переносятся все элементы вершин о, и о (вместе с выходящими иэ них дугами). Если после этого окажется, что вершнна о в г2 знает обе логические константы О и 1, то положим г' =- 1, иначе з' = з2. Как показывает пример на рис.
7.9, эффект теста — это, вообще говоря, не дистрибутивный преобраэователь обобщенных сетей. Действительно, для иэображенных на этом рисунке обобщенных сетей в1 и з2 имеем (1 = р (х)) (в1 Л г2) чь ((1 =- = р (х)) в1) Л ((1 = р (х)) г2). Л е м м а 7.5. ЭфФект теста <Ь = р (х,..., х„)): л'- М' — монотонньйь преобразователь, т. е. чв, г' ~= 2' УЬ в= (=(О, 1) УрЕУ Ухи..., х в~=У «» з' =+ <Ь = р (,..., „)> в ~~ < Ь = р (х,..., х„)) в'. Д о на за тел ь с т в о непосредственно вытекает нэ определения эффекта теста. ~ ] Л е м м а 7.6. Пусть в~= Я' и йеп (б, и) = аввегь (г) длл пути и е П, еедушево к распознавателю А с ус ювием л. Тогда йеп (П, иАе) = аввегь ((Ь = л) г), где е — вмходкирив из А Ь-дуга. Рпс.
7.9. Коатрпрвкср, опрооергоющай двстрвбутаваость эффекта теста. Д ока за тел ь от в о также непосредственно следует из определения аффекта теста и оаначает его содержательную корре ос . С] Итак, мы можем сформулировать задачу глобального анализа произвольного фрагмента С. Мы описали полурешетку (Я', /~), удовлетворяющую условию обрыва цепей, а также семейство монотонных преобразователей. В качестве началыюй разметки р, возьмем начальную разметку р, описанную в п.
2.3 главы 6. Семантическую функцию определим так: (ах = т) з, если дуга е' ведет к оператору хо = т, а дуга е выходит из него; (Ь= я) з, если дуга е' ведет к распознавателю с условием я, а е — его $$-дуга; $, в остальных случаях. ггг (з) $49 В силу леммы 2.2 для описанной задачи глобального анализа существует стационарная разметка р. Т е о р е м а 7.6. Дла любого фрагмента С, ззо дуги е и спипзиокариой разметки $г $птаз (С, е) и аззег$ ($г (е)). Д о к а за те л ь с т в о.
Пусть Š— множество входов фрагмента С, а я„и Н вЂ” преобразователи обобщенных сетей, определяемые по семантической функции ) как в и. 2.2 гл. 2. Используя леммы 7.4 и 7.6, получим $нтаг(С,е) = П яеп(С, гз) = П Д аззег$(з„(р (е')))= аамгз отек внмарш(г'. Н = аззег$ (Н (з)), для любой дуги е фрагмента 6. В силу теоремы 2А стационарная разметка р фрагмента 6 бевопасна, т. е.
Уе р (е) ~ Н (е), поэтому аввег~'(р (е)) с:. аввегь (Н (е)) = гпчаг (6, е). ( ) Будем говорить, что распознаватель А формально Ь-избыточен, если при стационарной разметке р (Л = ал) р (е) = р (е) для каждой из дуг е, ведущих к А. Из теоремы 7.5 вытекает следующее С л е д с т в и е 7.2.
Всякий Яормально й-избыточный распо.знаватель содержательно а-избыпигген. Теперь мы можем сформулировать новую эффективную схему правил преобразования фрагментов стандартных схем. Ф1 (Удаление избыточного теста). Пусть распознаватель А с условием ал во фрагменте 6 формально Ь-избыточен, к нему ведет ровно одна дуга е, а фрагмент 6' получается нз 6 заменой Тогда 6 6'. Т е о р е м а 7.6.
Если Фрагмент 6' получается из фраамента 6 применением схемы правил Фз, то 6 — 6'. Д о к а за тел ьс тв о непосредственно вытекает ив следствия 7.2. П 2.3. Освобождение сквозных схем. В этом разделе мы покажем, как с помощью эквивалентных преобразований преобразовать произвольную сквоаную схему в свободную сквозную схему. Первый шаг преобразования состоит в приведении схемы, которое описано в предыдущей главе.
Понятно, что приведенная схема "также будет сквозной. Если на одном из последующих шагов будут нарушены условия приведенности, мы снова добиваемся нх выполнения, не оговаривая этого особо. Луч А приведенной сквовной схемы Я, который ведет от распознавателя А к (другому нли тому же самому) расповнавателю В, называется второстепенным, если чу~арг(В) 3л~арг (А) г(ю, у) = а; где ю — путь по всем операторам луча Ь, Все остальные лучи схемы 8 называются глазными. Логическим гбрагментом схемы Я (короче: л-Фрагменпым) будем называть всякое вхождение в Ю 150 такого фрагмента, который не содержит ее главных лучей. Довольно очевидно, что для освобождения схемы 8 достаточно научиться освобождать ее макснмальные свявкые л-фрагменты. Все распоанаватели такого максимального свяеного л-фрагмента б имеют одно и то же количество аргументов, а действия, выполняемые над аначениями аргументов расповнавателей при любом вычислении по 6, могут состоять только в перестановках этих акачений (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
