1626435695-d1df5d2e6d953ce7ad4b4ccb5f4f4e30 (844296), страница 31
Текст из файла (страница 31)
Заметим для этого, что по построению автоматов Л (8) любому префиксу произвольной цепочка операторов в схеме Б соответствует слово в алфавите У, допускаемое автоматом А (Б). И наоборот, любому слову, допускаемому автоматом, соответствует некоторый префикс некоторой цепочки операторов в схеме. Обозначнм через С» (8) множество всех префиксов множества цепочек С (Я. Очевидно, что С (8«) = С (8«) тогда и только тогда, когда С» (Б«) = С» (Б«). Поэтому схемы Б«и Б«издморфны тогда и толъко тогда, когда эквивалентны ав- С СтаРт (ад] АРТ <Сса2 И ,У2 (Рь*2 [У, Е2 И" 12 1~" Р2 (Р,.з) Иъ.Р2 а стоп (л;,у2 К( Рвс. 7.1.
Првзвзз нестроевая ззтокатз Я (8) томаты А (81)и А (8з2. Алгоритм распознавания эквивалентности конечных одноленточных автоматов был описан в главе 3. Д С л е д с т в н е 7.1. Пробссма интсрярстационнссо взомор 4иава разрсишма с влассс свободных свкшдартнмх схем. Д о к а з а те л з с т в о. В силу леммы 7Л интерпретационный изоморфизм свободных схем равносилен изоморфизму, который, как толзко что доказано, представляет собой разрешимое отношение эквивалентности стандартных схем. [1 Рис.
7.2. Стоявартиме схемы и моделирувваие их автоматы: а — схема оья 6 — схеме Я~.е, в — автомат А (Ята); е — автомат А (8ь,) Итак, мы установили разрешимость проблем пустоты, тоталь- ности и интерпретационного изоморфизма в классе свободных схем. Однако эффект этих результатов снижает тот факт, что са- ма проблема свободы не является даже частично разрешимой (см.
теорему 5.4). Не существует и алгоритма, с помощью которого можно было бы произвольную стандартную схему преобразовать е эквивалентную свободную схему (831. В частности, для следую- щей схемы Ят. не существует эквивалентной свободной схемы: (старт, х:=а, У:=Ь, 3: если р (х) то 4 иначе 5, 4: % = 7 (х) па 3, 5: если р (у) те 6 иначе 8, 8: х:= б(х), 7:у:=УФ б; 8: степ (х)) Задаинеул. А. Докажите, что множества пращ»л преобразования, порождаемых оввс»изыми в и. 3.1 гл. 6 схемами ЛТ» (удалевве недаствжвммх) и ЛТЗ (сялеазание копай, нлн напнразэнне), представляет собой полную систему преобразований для отношения взамар4»»эма стандартных схем (а тем самым н волную систему преобраэавэввй для а»ношеная натерпретацвонваго изоморфизма свободных стем).
Б. Назовем схемы б» и б» в базисе Я иеовииеииорФииии, есле совпадая»» множества всех конечных цепочек операторов зтвх схем, и ии»оериреои»- Чиоиио иеоэииеоморЯимии, есле для любав интерпретации 1 базиса Ю результаты выполнения программ (3», 1) н (8», 1) либо одновременна ие анредеаевм, лабо определены в соответствующее ватерпре»ацнн 1 наиечвые цепачин операторов совпадают. Паважвте, что отношение интерпретационного кэаэввзомарфизма стандартных схем ве является частвчва рээрешшя»ы, нзэзввзамарфнзм стзвдэртвых схем разрешим, з для свободных схем интерпретационный кзззвнзамарфнзм равносилен кээзннэомарфнэыу.
В. Докажите, чта маши»ство прзвнл ну»образованна, параждаеымх схемэмн нрэвнл ЛТ(, ЛТ2 н ЛТЗ пз предыдущей глэвм, представляет собой полную систему преобразование для отношения нвэзвизомарфазмз стандартвых схем. $2. Сквозные схемы В этом параграфе мы выделим подкласс стандартных схем, называемых сквозными, для которых опишем алгоритм распоанавания функциональной эквввалентностн.
Интерес к классу сквозных схем в нашем изложении обусловлен тем обстоятельством, что он содержит несколъко различных подклассов, разрешимость эквивалентности в которых была установлена в разное время н разными методами (см. обвар в конце главы). 2Л. Определение снвазпых схем.
Класс сквозных схем выделяется как подкласс стандартных схем за счет двух ограничений, накладываемых на структуру информационных связей. На базис схем никаких ограничений прп этом не накладывается. Тот факт, что терм»» является подтермом терка т, будем записывать как и -С т. Например, х -ч, '1 (х), й (х) -~ б (х), но ) (у -~ (1 (х)). Стандартная схема называется схемой со сяоозными тестами, илп коротко скеоэыай схемой, если для нее выполнены два следующих условия.
Рз. Для всяких распознавателей А, В, лежащих на некотором пути от входа к ваключителъному оператору, и для каждого пути ш, ведущего от А и В и содержащего толъко операторы присваивания, справедливо Ух~ арг(А) Зуб= арг(В) х-о',1(й, у). 02. Для всякого распознавателя А, для всех пар х, р раалнчвых аргументов вершины А и для всех путей, ведущих к А от входа схемы, выполнено Ф (ш, х) чь Ю (ш, у). Пример двух (эквивалентных) сквоыых схем приведен ва рве. 7.3.
Рве. 7.3. Дзе звзаззлевтаме еввоэвме схемы Условие В1 означает, что в вычислениях сквозных схем не теряется нн один из тернов, на которых проверяются условия распознавателей. Если, например, р (ом..., о„) и д (гм... ..., т ) — два следуюшвх друг за другом теста вычисления сквозной схемы при некоторой свободной интерпретации, т» тт Зу о, -С тп Легко понять, что свойство В$ является эффективно распознаваемым.
Условие В2 означает, что в вычислениях сквозных схем прв свободных интерпретациях иредикаты проверяются только ка наборах попарно различных тернов. Нетрудно видеть, что проблема проверки условия В2 алгоритмнчески неразрешима. К ней можно свести проблему тождества слов Поста. Действительно, пусть (Н, Н ) — система Поста, Н, = ( „..., „), Н, = (()„..., б ). Приведенная на рис.
7.4 схема Я (Н, Нз) удовлетворяет условию В2 тогда и только тогда, когда система (Нм Нз) не имеет ни одного решения. Отметим, что схема 8 (Нм Н ) обладает свойством Вт. Кроме того, схема 8 (Ны Н ) свободна тогда и только тогда, когда систе- $42 Рис. 7.4. Схема 8 (77„Не) ма Поста (Н„Нв) не имеет решении. Это означает, что в классе схем, удовлетворяющих условию Р$, неразрешима проблема свободы. Что касается класса стандартных схем, удовлетворяющих условию 02, то он, очевидно, содержит класс,Ум для которого, как показано в гл. 5, проблемы пустоты и зквивалентности не являются частично раврешимыми. 3 а д а к и е 7.2. Докажете, что схемы, приведеикые иа рис.
7.8, фувкциовавьио вквивалевтаы и удовлетворлют условию Вт, причем схема йь °вЂ” сквовваа, а Лье — иет. 3 а давке 7.3. Докажите, что длв аесвободиой схемы иа рвс. 7.8, удовлетворавацей условию Вт, ио ие Р2, ие существует фуикциовальио еквиввлевтиой свободной схемы. 2.2. Обобщение иивариаитев. Если выходная дуга распоанавателя ведет к распознавателю с тем же условием, что и у первого распоанавателя, то второй распознаватель избыточен, его можно уделать с сохранением зквивалентности (см.
рис. 7.7). Чтобы сформулировать такое преобразование в более общем виде, ниже мы обобщаем понятия ииварианта и сети, введенные в предыдущей главе. Логическое выражение я назовем Ь-избвпюсчнм,в «а юрии ш, если и = и~хАш, где А — распознаватель 'с.условием па, я!7(и, лт)/лт,..., С(и, х„)Ьо] = ох И(шт, хт)йт...- ..., Ф (шт, х„)/и„); лт, ..., х„— все переменные, встречающиеся в я и оа, а йуть юв начинается Ь-дугой распознавателя А. Д43 Рнс. 7.5. Энвновлевтвые схемы 8в ° н Яве Рвс. 7.6. Схеме отло длн которой не существует внввволевтвой свободной схемы Множество утверждений, порсвкдаемое путем и во фрагменте б, обобщается следутощим обравовп беп (6, иФ = бед (а, то) О Д (Ь = и ] Л е= (О, Ц и логическое выражение и Л-ивбмточно на пути и).
$44 Рзс. 7Л. удазгазв взбнточзого васиогзаватаза В качестве обобщенного ингирианта дуги е фрагмвита б возьмем >очаг (б, е) = П реп (6, и>), аЮГ где пересечение, как в п. 2.1 предыдущей главы, берется по всем путям >о, начинающимся входами фрагмента сг и кончающимся дугой е. Итак, кроме утверждений-равенств вида г = — т, где з <:= ~= Ю, т Е= Т, обобщенный инвариант может содержать также зтгерждения логического типа с> = р (т„..., та), где Ь е— : (О, 1), р е— : У, т„..., т„б= Т. Распознаватель А назовем содержательно й-игбнточнмм, если его условие оа является й-избыточным на любом пути, начинающемся входом фрагмента н кончающемся дугой, ведущей к А, т.
е. (с> = аа) е= >пчаг (б, е) для всех дуг е, ведущих к А. Легко видеть, что если распознаватель А содержателыю с>- избыточен, то всякое вычисление, достигшее распознавателя А, всегда будет продолжаться выбором одной и той же >а-дуги этого распознавателя. Это значит, что распознаватель А можно удалить иэ фрагмента. В предыдущей главе был описан алгоритм разметки, который позволял эффективно строить инварианты дуг во фрагментах стандартных схем.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
