1626435695-d1df5d2e6d953ce7ad4b4ccb5f4f4e30 (Котов, Сабельфельд 1991 - Теория схем программ), страница 9

Не существует алгоритма, которнй строи.г би точное решение для генкой задачи глобального анализа. Д о к а з а т е л ь с т в о будет получено сведением проблемы тождества слов Поста (см. и. 2.3 в гл. 1) к некоторой задаче глобального анализа. Пусть (Х, У) — система Поста Х = (а„... ..., и„), У = ((),..., р„], где аи ()г — слова в алфавите (О, Ц. Зафиксируем полурешетку свойств Х = (О,Я()(0,()гХ(0, ()г, х/~у= Такая операцая пересечения, очевидно, коммутативна, ассоциативна и ндемпотентва, а длины всех строго убывающих цепей в Б ограничены числом 2, поскольку х ( у воаможно лишь при х = 9.

Зафиксируем монотонные функции окружения. р = (ы, »„»„у„..., у„), 34 т1(( ~ 3 <, и) 1та, р б=(0, 1)» а ((сВ, ())) = (аа1, рр1), б1 (9) = 9. б1 (~В) = 5' Ух (-=- 'Х 1л (х) = х' Ух я Ь Ь, (х) = 5; Ь, (9) = О, Ь, (Я = 5, та, ()е=(0,$)» Ь ((а,()))=$ Для доказательства монотонности функций Ь и я1 (1 = (,... ..., и) будем использовать тот факт, что х( р для х, у (= А влечет х = О. Поэтому х(у~ЬВ (х) =Ьз(9) = О~;ЬВ(р) а ° ° ае и х е у + б1 (х) = б1(9) = О ~( б1 (у). Монотонность функций Ы и Ь1 э„ ° ° -ь, очевидна — они даже дистрибу- с гиены.

В качестве анализируемого графа рассмотрим граф Г, изображенный на рис. 2.4. В этом графе ровно 2в +1 дуге которые рвс. 2.4. Граф Г мы обозначнлн соответственно а1,..., а„(входы), Ь1,..., Ь,1 (внутренние дуп1), с (выход). В качестве начальной разметки р» возьмем т11 (( ~( 1 ~ в) (В» (а1) = (а1, ()1). (Во (Ь1) = ре (с) = 5. Семантическую функцию определвм следующим образом: для ВСЕХ 1,У((е $, У~~;11) е В е В е ее В1 /В,' = /В1 = А, У 1 — — У,' = УВ1 = Ь1, А' = У,' = Ь ° ~а, =), /е= 1бе Для доказательства теоремы осталось заметить теперь, что (е (с) = 5 для сформулированной задачи глобального анализа выполняется тогда и только тогда, когда система Поста (Х, У) не имеет ни одного решения. Описанное сведение позволило бы решать проблему тождества слов Поста, если бы существовал алгоритм решения об1цей задачи глобального анализа.

~) Несложная модификация описанного вылив сведения позволяет доказать и более сильное утверждение: существует окружение (Е, /~, Р), граф Г н семантическая функция / такие, что не существует алгоритма, который по всякой начальной разметке давал бы точное решение задачи глобального анализа графа Г в фиксированном окружении (е, /'1, Р) и для фиксированной семантической функции 1» йэ Условия, достаточные для того, чтобы можно было эффективно находить точное решение задачи глобального анализа, дает елэдуэ)щая Т е о р е м а 2А. Ее»и е окрцекении д»» ана»иеа еее яреобразоеао)е»и ееобев)е диетрибутиенщ то ежа))коварна» раелетка р, дает точное рея)ение задачи е»оба»ьноео ана»иеа, т. е.

те Е= Е р (е) = Н (е), Д о к а з а т е л ь с т в о. Учитывая безопасность стационарной разметки, достаточно показать т е б= Е р,. (е) .'> Н (е). Докажем для этого, что для всех достижимых раэметок )д графа Г имеет место те ~ Е р (е) > Н (е). Для началыюй разметки )де получаем .'ФеЕ=Е )де(е) = б,()де (е)) = Д /~ бу()де (е')) = Н [е). е'иа |дне|ерш и', с) Пусть зто утверждение справедливо для достижимой разметки р, а )д' получается иэ р применением правила разметки к паре дуг (е', е).

Тогда Фд'(е)= р(е)/|д1', (р(е')) е Н(е) /~/; (Н(е)) = =Н(е)Л/'( Л Л б (р (е.В= е,ив |динаэш [е„с) = Н(е) Л ( Д /~ Д'(б ()де(ед)))) ~ ,ил |||инеошд „| ) Р Н(е)/|, ( /|, /~ б (Ре(ед))) = Н(е) /|,Н(е) = Н(е). смл |||виаерш да. е) Для всех остальных дуг ед, отличных от е, имеем р' (ед) = = р (ед) ~) Н (е). ) ) Итак, стационарная разметка дает безопасное приближение к точному решению в случае общей задачи глобального анализа н точное решение в случае задачи анализа с дистрибутивными преобразователями свойств.

Для получения стационарной разметки можно строить разные детерминированные алгоритмы за счет фиксации порядка применения правила разметки к различным парам смежных дуг, а также за счет исключения таких применений правила, которые заведомо ие изменяют разметку. Нн)ке описан один из таких алгоритмов. А»еоривм А. Параметры алгоритма: граф Г", операция пересечения /~ некоторой полурепютки, удовлетворяющей условшо обрыва цепей; семантическая фувадция /; начальная разметка ре.

Ивициалнздщия. Объявить акдивнымв те дуги е' графа Г, для которых гедд:-окр(е') ре(е) ФЮ (ре(е)). 36 Итерация. Пока множество активных дуг непусто, повторять следующий Жаг итерации: взять активную дугу е", пусть х — ее пометка. Удалить е' иэ множества активных дуг. Заменить пометку р каждой иэ дуг е. смежных с е', на пометку у /~ у, (я) и объявить дугу с активной, если оиа изменяет при этом свою пометку. Выход алгорнтма: стационарная разметка графа Г. Заданно 2Л. Задачу глобааьаого авалнэа вааоаем аряяэа, есав понурешетка свойств содержат едашщу, а семавтаческая фупкцпя тамона, что ~' чь т ьь ввч (а) = кон (а'); обратной, если 2 ш Ь в )э + $ оь ьЬвач(э') = коп(а).

Сфеумулнруйтэ прямую задачу глобэльно1'о авалнэа с дастрабутпкпыма преобраэоаатеаямв свойств для нахождеяпя асах вершка графа, достшканых от некоторого эадаапаго подмвожестаа его вершка. Б. Сформулируйте обратную задачу глобального авалаэа с двстрабутнааымя преобраэоаатеяямн свойств дхя вахождеаая асах эершпн графа, от которых ает на одного луга к некоторому заданному подмножеству вершка походного графа. 3 а д а в н а 2.2. Для каждан дуга графа указана ее длань — векоторое поэояаиеаьвее число.

Весом путе назовем сумму дава состаааающкх ого дуг, а расстоянаем между аершанамв э1 в иь — маавмальаый среди всех путей, аедущвх ст и~ к пг Сформуларуйте прямую задачу глобааъаого .аналаэа с днстрвбутвааыма преобраэоэатеаямв свойств дня аахождевая расстоявнй ет векоторев аыдааенной варшавы до каждой аэ остальных аершаи ь рафа. Краткий обзор и кемментаржи Метод рааметки впервые был использован А. П.

Ершовым И51 как средство сбора нелокалъной информации в схемах Янова. Килдел [И21 предложил алгебраизацию объектов-свойств и сформулировал алгоритм нахождения точного решения задачи глобального аналиаа в случае дистрибутивиости всех преобразователей свойств. Кэм и Ульман [1091 ввели понятие окружения для анализа и доказали алгоритмическую неразрешимость задачи аналиаа в общей постановке. Во всех этих работах рассматривались задачи одностороннего анализа, когда свойства вершины определяются свойствами толъко ее предшественников (прямая аадача) или, наоборот, только свойствами ее наследников (обратная задача). Попытка рассмотрения более общей задачи, когда 'свойство вершины графа может зависеть как от свойств наслед:ников, так и от свойств предшественников, была предпринята ::.Касьяновым [251, предложнвшим алгоритм ее приближенного ре';шения прн дополнительных ограничениях на структуру свойств.

[[.)бобщение задачи глобальиоуо анализа, описанное в настоящей ',::главе, было предложено Сабельфельдом [бб[. Приложения метода !-,,'разметки к задачам нахождення конкретных свойств схем про~рами будут описаны в последующих главах книги. Что касается ,,урафок, то литература по атой тематике весъма обширна. Назовем ;::4щесь лишь несколько наиболее известных монографий [5$, 20, 751. гллвлз КОНЕЧНЫЕ АВТОМАТЫ Исследования понятия вычислимости, формализованного в 30-х гг., развивались в дальнейшем в двух главных направлениях.

Первое свяаано с более глубоким изучением и анализом самого понятия вычислимости, с установлением его связи с основаниями математики. Второе направление стимулировано появлением вычислительных машин и широким практическим использованием алгоритмов в виде программ для ЭВМ. Это направление связано с конструированием и изучением понятий менее общих, чем вычислимость, с тем, чтобы сконцентрировать внимание на «более разрпшвмыхэ проблемах, решение которых могло бы дать практический эффект. С этой целью были предложены классы абстрактных машин, более простых, чем машины Тьюринга, например, конечные автоматы Рабина и Скотта [1331. Эти и аналогичные им автоматы беднее в средствах, но обнаруживают ряд полезных свойств, непосредственно используемых в теории схем программ и в теории формальных языков, и имеют довольно элегантную математическую теорию.

Мы не ставим себе целью изложить подробно зту теорию, а ограничимся лишь определением некоторых типов конечных автоматов и выделим ряд результатов, необходимых далее. Более подробно мы рассмотрим здесь класс многоленточвых автоматов и реаультат Берда о разрешимости зквивалентности двухлевточных автоматов, $1. Одноленточные автоматы $Л.

Определение автомата. Конечный вднолснтвчный (односторонний, дстврммнирвванний) автомат над алфавитом У задается набором А = (У, ф, К, д«, ф, 1) и правилом функционирования, общим для всех таких автоматов. В наборе А г — алфзвит; д — конечное непустое множество состояний (~ П р = и); Л С: 9 — множество выделенных гаключитсльнмя состояний; дз — выделенное начально« состояние; ф — «нуствйэ символ; 1 — программа автомата, представляющая собой множество команд; команда — зто слово вида аа д', в котором о, д' с= 9, а ~ У, и для любой пары (о, а) существует единственная команда, начинающаяся этими символами. Неформально конечный одноленточнмй автомат можно представить как абстрактную мешину, похожую на машину Тьюринга, но имеющую следующие особенности: а) выделены эаключительные состояния; б) машина считывает символы с ленты, ничего на нее не эапнсывая; в) на каждом шаге головка автомата, считав символ с ленты и перейдя согласно программе в новое состояние, обязательно перв- двигается вправо на одну клетку; г) автомат останавливается в том случае, когда головка достигнет конца слова, т.

е. символа 4р. Говорят, что автомат допускает слово а в алфавите г, если, начав работу с лентой, содержащей это слово, он останавливается в заключительном состоянии. Автомат А эадает характеристическую функцию множества М,~ дояргласимл ил слов в алфавите У. Действительно, его работу можно рассматривать как процедуру распознавания того, принадлежит ли заданное слово множеству Ма, если свяэать с остановкой в эаключвтелыюм состоянии символ 1, а с остановкой в незаключвтельном состоянии — символ О. Поэтому говорят также, что автомат А определяет множество Ма. Однако не для всякого раэрешимого множества можно построить определяющий его автомат Напрвмер, множество всех правильных слов в алфавите ((,)) (см.