1626435695-d1df5d2e6d953ce7ad4b4ccb5f4f4e30 (844296), страница 47
Текст из файла (страница 47)
9.5), где Х, — метка оператора петля, нового оператора, добавляемого в р-имитатор. 7 Г Таким образом, каждая метка оказывается закодированной словом длины т в алфавите (а, Ь), и смысл описанных замен операторов становится понятным. о Построение р-вмитатора схемы Бь для И Д1 и-местного предикатного символа р осуществляется точно так же, но вместо констант а и Ь используются 2я констант: ~г а„..., а„и Ь,,..., Ь„. Соответственно увеличивается число переменных и операторов присваиванвя в правилах замены.
Ря>ь Отметим, что в схеме Бг, использование переменной ш ограничено: она не входит г.„ д в распознаватели и взаимодействует с магазином так, что ей никогда не может быть присвоено значение, отличное от меток из жвй „астру,'щ„„,, (А„Ем . „., А ). Поэтому несложно убеээ и. даться, что предлагаемое преобразование схемы Бь в р-имитатор дает схему иэ Я (1М), эквивалентную схеме Б,, но с одним ограничением: схема Бь и ее р-нмитатор эквивалентны только на тех интерпретациях 1, в которых 1 (р) (7 (а)) =- О и 1 (р) (1 (Ь)) = Ф.
р-имитатор схемы Б э изображен на рис. 9.6. Так как в схеме Бэ.з переменная ш запоминает только три метки хм х.э и Ь|, мы упростили пример, не включив в область значений этой переменной другие метки. Построение локатора. Чтобы исключить упомянутое ограничение, используется локатор. Локатор Б г~е Рис. 9.6. Р-вввтатоР схемп Льл зто схема из класса К ($М), задача которой — для любой интерпретации 1 обнаружить в схеме 8ь преднкатный символ р)"», 1 ~ ч~'. г ~ Й, и пару наборов значений аргументов (Им ..., Й„) н (4,...,4,) такие, чтобы 1 (р,) (4,..., й„) чь 1 (р~) (Нг,..., И ). Найденный преднкаткый символ н пара наборов значений аргументов будут в дальнейшем использованы в имитаторе вместо рассмотренного выше произвольного предвкатпого символа р н констант.
Более точно, локатор 8„для схемы 8ь, построенной по схеме с процедурами, обладает следующими свойствами: а) если для некоторой интерпретации 1 в протоколе выполныия программы (8ь, 1) нет повторного вхождения какого-лкбо предиката 1(р) с разными вычисленными значениями, то программа (8ю 1) останавливается с результатом та) (8з, 1), если и только если останавливается программа (8ь, 1), причем та) (89, 1) = та] (8ь, 1); б) если для некоторой интерпретации 1 првдккат 1 (р)ю) вычисляется дважды при наборах д„..., И„и И;, ..., и'...
а 1 (рд (И„..., 4,) = О и 1 (р,) (4„..., 4,) = $, то в локаторе 8з выполнявпся следующие действия: 9 В. и. котаз, в. к. свбап4ельз 247 (т) добавленным в локатор переменным и„,..., и „присванваются значения, соответственно: Им..., до„ (2) добавленным в локатор переменным и»„..., и»„присваиваются эначепия, соответственно: дп..., Н„; (3) осуществляется переход к выполнению добавленного в локатор оператора Х»«: петля, где Х»« — новая метка. Локатор для схемы 8ь строится следующим образом (для простоты все предикаты р» р»,..., р„в схеме 8г. считаем одноместными, обобщение делается очевидным способом): а) по рекурсивной схеме нли схеме с процедурами, из которых получена схема 8ю строится приведенная схема с процедурами (см. гл.
8, и. 4.2); б) прнведенкая схема транслируется в схему 8г. с помощью алгоритма из леммы 9.1, и ясно, что схема 8ь эквивалентна схеме 8ь; в) каждый условный оператор вели р, (х) то Ь«иначе Х,» заменяется фрагментом, показанным на рис. 9.7; г) из полученной схемы удаляются юбю все операторы, содержащие магазин 1 О и выделенную переменную и, и затем все операторы, иэ которых нельзя г«[ом ыю попасть к заключительному оператос о ру, а «висячие» дуги присоединяются к оператору петли, оа Построенный таким образом локатор принадлежит классу У и действительно обладает теми свойствами, 1 .
п«тл« которые былк для него запланирова- ны. Свойство а) обеспечивается тем, Рвс. зл. Фрагмокт локатора, что, в случае отсутствия в процессе замоккющвй условный опора- выполнения программы (8ь, 1) потор вторпых вхождений предикатного символа р~ с разными значениями ! (р,) (о) н Х (р~) (И'), выполнение программы (8«, 1) протекает так же, как и выполнение программы (8ь, 1). При этом исключение из схемы магазина и операторов с переменной в не влияет на работу программы (8, 1), так как в атой программе нет повторных рекурсивных вызовов функций и, следовательно, нет необходимости запоминать контекст возврата (см.
лемму 9.3). Свойство б) обеспечивается тем, что как только для некоторого символа р~ будет обнаружено месовпадение 1 (р ) (о) Ф 1 (р ) (И'), произойдет переход на оператор Х +;. петля. Отсутствие магазина, переменной ю и использующих их операторов ве влияег на поведение локатора и в этом случае, так как прежде чем понадобится осуществить возврат к месту вызова, обязательно обнаружится повторное вхождение р, с отличным от предь|дущего значением предиката Х (р,) (см. лемму 9.3) и осуществится переход к оператору Х +,... петля. При этом значения»У(и,) и»г'(и») переменных и Ркс. 9.8.
Локатор для скоки Бал и ка таковы, что 1(р~)(И'(и ) =О, 1(р,)($К(иа)) = $. Локатор длк схемы Яа„а нэображен на рис. 9.8. Он пострееи по приведенной схеме с процедурами, полученной частичной травс- ющией схемы Яа.аа (см. также докавателаство леммы 9Л), а прв- ведениак схема имеет ввд (старт (х), Ф: ха:=х, 3: если р (х,) те 3 иначе 4, 3; иа:=ха на 9, 4: *а . = 8 (хт), 5: ха."= р(з1), 6: иа:= й(хт), 7: и,:= Г(и,), 8- оа = 1(х и) 9:у: от~ $0: стен (р)) ат (х) = (старт, $; если р(х) те 2 иначе 3, гв 2:и:=х ив 6, 3: з:=у(х), 4: з:=Г(х), 5: и:=Ь(х), 6: в:=Г(и), 7: и:= 1(х, и), 6: стоп (и)). С б о р к а с х е м ы Я.
Результирузвцая схема 8 из класса ,У(1М) собирается из локатора Яз и р1-имитаторов схемы Яь. Схема 8 начинается локатором Яю за которым следуют риимитаторы 8„8,..., Я„, где й — число предикатяых символов в схеме 8ь. Однако как в локаторе, так и в ргимитаторах делаются изменения, превращающие эту последовательность схем в одну схему 8.
Для каждой переменной у~ из памяти схемы 8ю пе считая выделенную переменную и, добавляется новая переменная и„ и локатор начияается серией пересылок, назначение которых— запомнить качальное состояние памяти, которое, возможно, понадобится для р,-имитатаров: (старт(уг у ° - ° .). и1:= уп из:= уз. ° .). В каждом р~имитаторе оператор старт заменяется последовательиостью операторов: 1~+~: Уг:= ит Уз:= ит а иэ локатора удаляются все операторы 1 „. "петля.
Таким образом, схемы 8„8„..., 8» оказываются присоединенными к схеме Яз. Далее, в каждом р1-имитаторе константы а и Ь, где бы ми встречались, заменяются иа переменные и и, соответствеппо, из иэ локатора. (Эти переменные и переменные и~ являются единствеииыми зглобальными» переменными схемы 8.) Построенная магазинная схема 8 из класса й". (1М) эквивалентна схеме Яь.
Действительно, для любой интерпретации 1 первым пачвкает выполняться локатор. Если в процессе его выполнения ке встретился дважды одвк и тот же предикаткый символ с разяыми значениями предиката, то выполнение программы (8, 1) происходит точно так же, как и программы (8ю 1), если иэ нее удалить все операторы с переменной ю.
Выше мы видели, что в этом случае программы (Яю 1) и (Яю 1) или обе зацикливаются, или останавливаются с одинаковыми результатами. Если же встретилось повторное вхождение предикатиого символа р~ со аиачепием предкката, отличным от предыдущего, то осуществляется переход па начало р~имвтатора. При этом значения перейениых и и из сохраняются и восстанавливается начальное состояние памяти.
С этого момента можяо забыть о том, что выполнялся локатор, и рассматривать выполиекие программы (8, 1) как выполнение программы (8„1), в которой значения И' (и,) и гг'(из) перемеииых и и иь ие меняются, а предикат 1 (р,) дает разные значеиия: 1(р,) (ТФ'(и )) = О и 1(рц) (гг'[из)) = $. Как уже отмечалось, программа (8„1) эквивалентна программе (Яь, 1). П 2И Т е о р е и а 9ЛО (Грие — Констебль). Класси Рекурсивных схем и схем с процедурами транелирусвм в клаве магагииимх схем, в частноапи, в класс схем с одним магагииом, т. е. У (В) ~ ~,У (1М) и У (Р) ~( У (1М). Д о к а з а т ел ъ от в о. Алгоритм трансляции состоит в последователъном применении преобразования рекурсивной схемы в схему из класса У (1М, Х,) (см.
лемму 9Л) и преобразования полученной схемы в схему из класса У (1М) (см. лемму 9.4). Д Отметим, что предложенный алгоритм трансляции рекурсивных схем в магазинкые дает схемы, в которых нспользуютсн только два оператора над магванном — оператор ашиси и оператор выборки. Следовательно, для реализации рекурсии достаточно более узкого класса магавинных схем, а именно — класса У (ИХ) схем с одним магазином и без оператора проверки пустоты магазина, Установлено [8д), что классы,У (В), У (Р), У (1М) и,У (1М) равномощны. 3 а д а н в е 9.5.
А. Транслнруйде в магазвввые схемы ревурснвные схемы делд (см. гаванне 8.6), лд д н Яд.д (см. гл. 8, и. 1.2). Б. Проверьте, упрощаются лв полученвые схемы, еслн попользовать условный оператор проверни пустоты магагвва. Т е о р е м а 9.И. Класс магагинных стек не транслируем в класси рекурсивных схем и схем с щюцедуралди. Д о к а з а т е л ъ с т в о. Согласно теореме 9.1 существуют счетчиковые схемы, которые нельзя транслировать в рекурсивные. Но счетчнковые схемы транслируются в магазинные (теорема 9.6).
Если допустить, что любую магазинную схему можно транслировать в рекурсивную, то возникает противоречие. ) ) Т е о р е м а 9Л2. Класс магагиииых схем строго моирдее класса рекурсивных схем и схем с процедурами, т. е. У (М) ) У (дт) и У (М) ) Эд (Р). Д о к а в а т е л ъ с т в о. Следствие иэ теорем 9.3, 9.6 и 9ЛО. ) ) 2.6. Сраакнтельиая схемателогия. Для того чтобы получить полную картину соотношений между рассматриваемыми классами схем, остается сравнить дю модцности классы У (В) и У (А), У (с) и У (М), У (с) и Э' (А), У и,У (М),,У и У (А). Т е о р е м а 9.13. Класс схем с массивами строго моирдее классов рекурсивных схем и схем с процефрами, т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
