1626435695-d1df5d2e6d953ce7ad4b4ccb5f4f4e30 (844296), страница 23
Текст из файла (страница 23)
Схемы Лаврова удобны для выделения и анализа информационных связей в программах, а также для изучения взаимодействия зтях связей с логическими связями, описываемыми графом переходов [16]. В частности, схемы Лаврова были применены при исследовании проблемы автоматического распараллеливания программ [27[ н длк разработки алгоритмов оптимизации программ [59,8Ц. в.к.истов,в.н.сае Е ьа ГЛ АВЛ 5 НЕРАЗРЕШИМЫЕ СВОЙСТВА СТАНДАРТНЫХ СХЕМ В предыдущей главе были введены такие свойства стандартнмх схем, как пустота, тотальность, свобода, отношение функциональной зивввалентностп. Первый шаг в исследовании этих свойств схем — установление их распознаваемости. Мы убедимся, что проблемы пустоты, эквивалентности, свободы и тотальности для стандартных схем неразрешимы, более того, первые три проблемы не являютея частично разрешимыми. При доказательстве неразрешимости пустоты и эквивалектности будем следовать Лакхзму, Парку и Петерсону [119), использовавшим метод сведения проблемы пустоты двухголовочных автоматов к исследуемым проблемам.
Причем неразрешимость будет установлена уже для довольно частного подкласса стандартных схем„базис которых содержит лшнь дзе переменные, константу и по одному одноместному функциональному и предикатноиу свмволу. Неразрешимость проблемы свободы устанавливается также методом сведеивя с привлечением проблемы Поста. й 1. Двоичный двухголовочиый автомат Для доказательства неразрешимости проблемы пустоты и эквивалентности будет показано, что стандартные схемы могут моделировать (в уточненнои ниже смысле) двухголовочные автоматы, что позволит свести проблему пустоты зтнх автоматов к проблеме пустоты схем. Такое моделирование можно осуществить более простым способом, если использовать специальный класс двухголовочных автоматов, а именно класс двоичных автоматов, работающих ео словами над алфавитом (О, 1).
Следующая лемма устанавливает связь между классом всех двухголовочных автоматов п подклассом двоичных автоматов специального вида. Л ем ив 5А. Сущеетгугт алгоритм пргобрагогания дгухголооочных аотанатоо о дгоичныг дгухголовочнмг агтоматм, сохраняющий пустоту агтоматог (построенный двоичный автомат Аь пуст тогда и только тогда, когда пуст исходный автомат А). До ка з а тел ь от в о.
Пусть двухголовочный автомат А иад алфавитом У = (а, а, ..., а„) имеет мпожествдьсостояиий 9л = (ф', дг, ..., д„г), где верхний индекс равен 1 (активна головка 1) илн 2 (активна головка 2). Преобразование этого автомата в деон шый начнем с коднровки символов и слов из уз 96 словами в алфавите (О, 1) по следующему правилу: код (4~) = О; „н ив= ~т... ( о »=1, и < н) — — т ( ) т ( д. Так как символ 4~ кодируется нулем, любому непустому слову на ленте автомата А соответствует двоичное слово на ленте автомата А„, оканчивающееся двумя нулями.
Автомат останавливается, прочитав два нуля подряд (или О, означающий пустое елово). Автомат А преобразуется в двоичный автомат Ав (оба представлены графами) следующим образом. Каждый фрагмент графа ет авн Ст ввнлютнтельнын нтврын 'сеатонний с с езанлмнителннын ын свет»нина б в Рао.
ЬЛ. Фрагмеатм даулгоаоаочяого автомата А я ааоачного автомата Ае. е -- фрагмеат автомата А; 6 — соответствующий фрагмеят автомата Ав; ив отвергающий фрагмевт; в — доаусяавщай фрагмент автомата А, соответствутощий некоторому состоянию д,' из ()л в. показанный на рис. 5Л, а, заменяетса фрагментом графа автома. та Ад, показанным на рис. 5Л, б (верхние индексы у символов состояний, указывающие номер активной головки, опущены, когда зта информация несущественна; однако следует иметь в виду, что оня сохраняются при аамене фрагментов). После того, как последовательно проведена замена всех фрагментов тапа фрагмента на рис.
5А, она соответствующие фрагменты типа фрагмен- 4» 99 та на рис. 5Л, б, к графу добавляются фрагменты, показанные ва рис. 5.1, в н 5Л, з. Множество состоянии автомата А„включает: а) вез старые состояния из Дд; б) для кахщого старого состояния д,' и новых состояний, гдз и — число символов в г'„ в) дза новых состояния г1 и гз. 1 1 Заключительными состояниями автомата А являются все заключительные состояния автомата А и только они. Вершины з, (остапов допускающий) и з„(остаяов отвергаю щий) носят вспомогательный характер в графе автомата Аы Они отмечают тот факт, что автомат прочитал два нуля подряд и остановился в заключительном состоянии (случай з,) или в незаключительном состоянии (случай з,).
Сравнение фрагментов на рнс. 5Л, а к 5Л, б показывает, что если головка 1 (1 =- 1, 2) автомата А, находящегося в состоянии д~, обозревает символ а„(1 «» й«» н), после чего автомат переходит в состояние д', то головка 1 автомата Аы также находящегося в состоянии д), обозревает первую единицу двончного кода символа аю после чего сдвигается вправо й + 1 раэ, переводя автомат последовательно в состояния зя, зн,..., зпн д„.
Когда ав- 1 томат Аь перешел в состояние о, его головка 1 обозревает первую единицу кода символа, стоящего справа от а„на ленте автомата А. Если же группа единиц на ленте автомата Аь не является кодом ни одного из символов из У, то автомат Аз переходит в не- 1 1 заключительные состояния гз н гз, из которых не выходит до остановки (фрагмент иа рис. 5Л, в). Если на ленте автомата А„ после коде символа из У стоит О, то автомат (находяеь в старом состоянии) останавливается и допускает (з,) нли отвергает (з,) двоичное елово в зависимости от того, является ли это состояние заключительным или нет.
Индукпией по числу состояний автомата А легко убедиться, что автомат А» допускает двоичное слово (3 тогда и только тогда, когда оно является двоичным кодом слова иэ уе, допускаемого автоматом А. Таким образом, иэ пустоты автомата А следует пустота автомата Аы и наоборот. Д П р и и е р. Двухголовочкый автомат А, допускающий только те слова в алфавите У =- (а, Ь, с), в которых символ а встречается не меныпее чнсло раз, чем символы Ь и с, вместе взятые, показан на рис. 5.2, а (заключктельное состояние — дз). На рис.
5.2, б изображен двоичный автомат, построенный по автомату А (10 — код символа а, 110 — код Ь, 1110 — код с). 3 а да вяз йЛ. Постройте дзовчвмй автомат во дзугхезозочзому автомату, иаобрзжеккому яз рве. 3.2. Л е и и а 5.2. Проблема пустоты двоичных двухзолозочнмх автолнплов нв лаезвтсн частично разрвнаьмой. Рмс. 5.2.
Пример доухголовочзого азтомата А и восгроемвого ио нему дсе- вчмого азгомага Ае До к а э а тел ь от в о. Достаточно применить метод свв денна с использованием теоремы 3.3 и леммы 5Л. ( ( б 2. Меделиреваиве двовчного' автомата стандартной схемой ЙЛ. Класс У~ стандартных схем. Зафиксируем класс Уг стандартных схем в следующем базисе %1: множество переменных — (хп хе»; множество функциональных символов — (а, Щ; множество првдикатных символов — (риац»; множество операторов — (х ."= у (хг), х:= У (х ), х:= а, хе ."= а, р (хг), р (хе), сток (хм х )». Кроме того, предполагаем, что в каждой схеме из класса Уг операторы засылки констант ветре ппотся только по одному разу в схеме, причем в самом начале, т.
е. все схемы иа класса Уе начинаются так: (старт, х:= а, х:= а,...). Отметки, что при любой свободной интерпрегации Х базиса Жг в любой программе (8, У), где Я ~ У, переменные х и хз могут принимать эначенкя только из следующего множества тернов: (а, (а, Ца, . „у "а,...) (Ы (термы представлены з бесс кабачной форме, а (" — слово 1~- -Л. 2.2. Построение схемы, моделирующем автемат. Двоичное слово Ь,Ь, ... Ь согласовано со свободнов интерпретацией базиса .Юг если для любого ю, 1 ~~ с ~~ н, 1 (р) (')'а') =- Ь;, где р— единственный преднкатный символ базиса Мг П р и м е р. Слово (03010100 согласовано с любой свобод.
ной интерпретацией ) такой, что для всех г ~~ 9 ~ 1, если ) нечетно и меньше 9, ( О, если ю четые или равно 9. Свободная интерпретация х такая, что для всех ю 1 (р) О'а') = — О, согласована с любым словом, не содержащим т, Для того чтобы свести проблему пустоты двоичных дзухголовочных автоматов к проблеме пустоты стандартных схем из класса,У,, покажем, что для любого двоичного автомата А можно построить схему 8 нз Рг„которая моделирует автомат А в следующем смысле.
Коли на ленту автомата А подано пронавольное двоичное гчово а, то программа (Б, 1), где Х вЂ” любая свободная интерпретация базиса Юп согласованная с а, останавливается в том и только в том случае, когда автомат допускает слово а. Л е м и а 5.3.,цвоичнмй двухмьиюочний автомат пуст в том и толью в том случае, если пуста моделируюисаа еео стпандартнал схема. Д о к а з а т е л ь с т в о.
Предположим, что автомат А пуст, а моделирующая его схема Я не пуста, т. е. существует свободная интерпретация 1 такая, что ф, е) останавливается. Этого не может быть, так как среди множества всех двоичных слов, согласованных с 1, нет слов, допускаемых автоматом А. С другой стороны, если предположить, что схема Я пуста, но существует слово а, которое допускается автоматом А, то схема не модглнрует зтот автомат (по определению). ~ ) Л е м и а 5А.
Длл любого двоичного двухголовочноео автаиата можно построитпь моделируюиую его стондарнтую схему из класса Рг Д о к а з а тел ь с т в о. Построение схемы осуществляется в два атака. Иа первом отаве заготазлнваютсв фрагменты стандартной схемы, из которых нз втором агапе собирается схема. И автомат, и схема считаются представленныин в трафовой форме.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
