1626435695-d1df5d2e6d953ce7ad4b4ccb5f4f4e30 (844296), страница 24
Текст из файла (страница 24)
Фрагмент графа — зто его подгрзф (подмножество вершин вместе с дугами. соединяющими зтк вершины). В рассматриваемых нин."е фрагментах выделена начальная вершина (в аз|нем случае — это вершина, в которую не заходит ни одна дуга, илн, н случае фрагменте с одной вершиной,— сама зта вершина). <Ррагиент может иметь вь|ходные дуги, не заходящие в его вер- Щ =Я % % »т»с» а стоп(х„.т ) ПЕТЛЯ Рпс. 6.3. »ррагмеатм ставдартаой схемы вз класса Уте а — фратмевт Я; „. 6 — слева фрагмент графа автомата (сост«апас те»), справа — фратмеат я'»е Я -- фрагмент Я +т, а — фрагмеат Я +Я' д — другой зарплат для фрапеевте Я а (оператор петле) асех схем иа класса Уе начальный фрагмент„представленный на рнс.
5,3, в. Фрагменты р», О ~~ у ~ и, соответствуют состояниям р» н строятся по фрагментам графа автомата, связанным »' с р»» так, как показано на рис. 5.3, б (обратите внимание на сост аетствие пометок выходных дуг фрагмента автомата н фрагмента схемы). Фрагмент 9 „+е соответствует вершине д„+е (см. рис. 5.3, е), фрагмент 3 „, — вершине р„,а (см.
рис. 5.3, а). При любой интерпретации выполненне фрагмента на рис. 5.3, з сводится к бесееонечному въшолненив распознавателя, независимо от логического выраження внутри него. Поэтому этот фрагмент эквивалентен оператору петля (см. рис. 5.3, д). 103 : 'шины. У стрелок выходных дуг есть специальные пометкк: в случае фрагментов графа автомата — символы состояний, в случае фрагментов схемы — номера фрагментов.
Пометки у выходных дуг нужны для сборки схемы иа фрагментов на втором этапе преобразования. Пусть граф двоичного двухголовочного автомата А вили»чает веРшины-состоЯннп (де, ф, ..., д», ..., РЯ) н Две вспомо«ательные вершины — останов допускактщий и останов отваргаеощнй. В докааателъстве леммы 5.т эти вспомогателъные вершины обозначались а и з„здесь же удобнее присвоить им «унифицированныее обозначения д„+е и д, соответственно.
Схема собиРаетсЯ иэ п + 4 фРагм™ентов з яа«„У е, з „ У»» ° » У и» У п»е» Хя+е. Фрагмент Уаૠ— общий для Нв втором агапе пз фрагментов Яз~, Яе, ..., К„.з собнрается стандартная схема нз класса У, по следующему правилу: выходпаи дУга с пометкой 1 фРагментов лвзт, Рз, ааводится на начальную вер|пнну фрагмента Кз, где О~уз а„п + 2. Остается перенумеровать подходящим образом все вершннм получешюго графа числами-меткамн, и стандартная схема построена. Работе автомата А над некоторым двоичным словом а соответствует выполнение программы (Я, 1), где Я вЂ” построенная схема, 1 — некоторая свободная зштерпретация базиса класса Э', согласованная с а.
Интуитивно зто соответствие состоит в следующем. Команда д~Ь -~ дз, где Ь вЂ” символ О вли $, заставляет авто. мат выполнить очередной шаг, состоящий из двух действнй— перехода в новое состояние в зависимости от прочтенного символа Ь н сдвига головки. Шагом выполнения программы будем счвтать выполнение фрагмента. Первый шаг — вьпюлнение начального фрагмента лево в рееультате чего значения обеих переменных лг и л становятся равными 'е'. Каждый шаг выполнения фрагментов К, ..., Я„ соответствует шагу работы автомата и также состоит из двух действий: сдвигу головки з соответствует выполнение оператора присваивании щ = 1 (1) (щ), переходу в новое состояние — выполнение условного оператора ! (р) (л;). Если автомат остановился в аанлючнтелъном состоянии, программа должна зыполиить оператор стон (л» хз) и остановиться.
Если автомат остановился в неааключителъиом состоянии, программа должна зациклиться, бесконечно выполняя фрагмент У' +з. Покажем, что построенная схема 8 моделирует автомат А. Мы установим индузщней по числу шагов работы автомата над словом а, что после любого шага Ь имеет место следующее соответствие: если автомат А после й-го шага перешел в состояние д~~, 0 ~1~ л + 2, а головки $ и 2 прочитали к атому времени префиксы Ь,Ь ... Ь, и соответственно Ь,Ьз... Ь слова а, то программа (о, 1), где 1 — согласованная с а свободная интерпретация, после (й + $)-го шага выполнила фрагмент 9'~, а $Уз+, (я,) = '1'а' н И'аы ('гз) = 7 а', где И~„, — состояние памяти программы после (Й+ $)-го шага. Б а з и с и н д у к ц и п.
В начальный момент (после зиулевого шагаэ) автомат находится в состоянии ф, обе головки не прочитали еще ни одного символа. Программа сделала один шаг (выполнен начальный фрагмент з',) и переходит к выполнению фрагвюнта рз, ЬФ'т (лт) = гт' (л ) = 'а'. Ш а г индукции. Пусть после Ь-го шага автомата имеет место предположенное соответствие между резулътатом работы автомата и результатом (Й + 1)-го шага выполнения программы. Покажем, что такое соответствие будет иметь место и после (Ь + + $)-го шага автомата ((Й+ 2)-го шага программы).
1. Пусть иа (Ь + 1)-м шаге автомат прочитал головкой г оче- 104 стппт Рз РСЮ 1 е а~с-йети степ <кпгт Дй РФЫ 1 ж-ач ок ИМ 1 рз РФМ Ф "йзЗ1 лк Дх; Р~г1 О 4 ию 1 Рсз11 о 'т: Усзв1 4 РРд 1 'л,: Рет:.,1 гзт РСЮ встя» РМ~ 1 Ряс, 5.4. Сзсмс, кодепярутяцзя потекет ап рзм. $.2. Возле зорвпш-рсскоз- апвптозоа омкясзкы соотзоюствующке состояаяя автомата редной символ Ь на ленте и перешел ив состояния рт и новое состояние д,т.
Для определенности положим, что 1= $. По построению стени значение переменной и, после (й + 2)-го шага программм станет равкмм T+за', а значение переменкой кз не иеменнтск. Терм '~'+'а' — вначение аргумента првдикзта 1 (р) во фрагменте Кп Так как слово а и скоооднам интерпретация 1 согласона- Мео яы, Х (р) ('Хсыа') = Ь. Поэтому па следующем шаге работы про. граммы будет выполнятъся фрагмент $,.
2. Если после й-го шага автомат остановился и л, — заклк1- чительное состояние, то, по построению схемы, программа перейдет иа (Й + 2)-м шаге к вьшолкенвю фрагмента й „,, т. е. выполнит оператор стоп (хм хз) в остановится с результатом та1 ф, Х) =- =- ('Х'а', '~ о'), где 1 илн т равно длине слова сс. 3. Кслв после й-го шага автомат остановился и д~ — незаключнтельное состояние, то программа перейдет к бесконечному вы полнению циклического фрагмента К„, . Таким образем, для любого слова ка ленте автомата н для любой свободней квтерпретацнн Х, согласованной с сс, программа (о, Х) останавливается, если автомат допускает слово а, и зацикливается, если автомат отвергает а.
Заметим, что если программа (8, Х) останавливается, то результат та1 (8. Х) — -- ('Х'а'. '~ а'), где шах (1, т) равен длине слова сс, ~] П р и м е р. На рне. 5.4 приведека стандартная схема, моделирующая двоичный двухголовочвый автомат, изображенный в» рис. 5.2. 3 а д а в и е 5.2. Постройте стовдзртоук схему ла класса 5'и модело рузздую дзозчвмй дзухголозочзий автомат зз задавил Ь.й 4 3.
Теоремы о веразрешвмых евойстваз стандартных схем ЗЛ. Проблемы пустоты п эквявалентпости. Т е о р е м а 5Л (Чакхэм — Парк — Патерсон). Проблеме пустоты стандартных схем но делается частично рлзреииьмой. Д ока за тел ьс тв о. Сведением проблемы пустоты двоичных двухголовочных автоматов (леммы 5.2, 5.3 в 5.4) к проблеме пустоты стандартных схем нз класса Ус нз множестве всех свободных интерпретаций устаяавлнваем, что последняя проблема ве является частично разрешимой. Из теоремы 4.2 следует, что проблема пустоты схем из класса,У ва множестве всех интерпретаций также не является частично разрешимой. Так как Уг — подкласс класса У всех стандартных схем, то проблема пустоты пе является частично разрешимой к в классе У.
Т е о р е м а 5.2 (Лакхзм — Пзрк — Патерсон, Летичозский)- Проблема фуьнйиона соней знзиоалгнтности .л~андартимх схслс ял ллллстсл часлисчно раарлиискай. До к а з а тел ь с та о. Денстввтелько, если бы зта проблема была частично разрешима, то существовал бы частнчныв алгоритм распознавания пустоты стандартных схем. который состоял бы в установлении эквивалентности заданной схемы заведомо пустой схеме, например, схеме Бъс, изобрансенкой яа ряс. 5.5. 3,2.
Проблема тотальности. Т е о р е и а 5.3 (Лакхэм — Парк — Петерсон). ХХроблакв тотальности стандартных схелс частично разреияьза. 106 Дока за тел ьс та о. Пусть Я вЂ” стандартная схема, С— множество всех префиксов допустимых цепочек схемы Ю (допустимые цепочки тоже входят в С, так как ояи являются префиксами самих себя). На множестве С введем следующее отношение с~э: с1~сз, если сз Е=С, сто= С, сз-ьсе и с является максимальным префиксом см т. е. для старт любого са Е= С и с, 4й с,, сз чь см не моя<от быть, чтобы с, ~ сз и одновременно с, с с .
Можно определить граф С, описывающий вто отношение. Вершинами его являются алементы С, и иа с, встав ведет дуга к см если и только если с, ( с,. Легко видеть, что граф С является деревом. Его корнем Рве- 5-5- ((у. служит префикс„состоял(ий иа единственной метки О; ив вершины с = (О, 6,..., й) исходит одна дуга, если Й вЂ” метка преобрааователя, одна нли две дуги, если й — метка распоанавателя, и ата вершина является листом, если и — метка ааключнтельного оператора. Таким образом, листьями дерева б служат допустимые цепочки схемы Я.
От- (6) метим также, что в С длина префикса с, ровно на (0,1) единицу меньше длины префикса с, если с, ( с,. Для схемы 8 (см. (ор,т) рнс. 4.3) дерево б покааано на рис. б.б. (0Д,2,6) (а,ц2,5) Если б — конечное дерево (т. е. количество его (ол,2,5,а) вершин конечно), то все допустимые цепочки конеч- (05,2.5,6,6) (ЕЬ2,5,6,5) ны и схема Я тотальна. В противном случае для (ец25656) (01 25А5)) етого дерева выполняются условия нелестной леммы (01 25 6 565) (01 2 5 652 2) Коняга (114), которая утверждает. если б — беско- (0,1,2,5,4,5.6,5.~) (01,2,ЗА5Д2,6) вершины которого исходит конечное число дуг, то в С (ед.2.5.~.5.6.5.2.2) существуез хотя бы один бесконечный путь, иачн- (0,1,2,5,6.5,6,5,7.2,6) кающийся в корне.
Так вак длины префиксов Рве. 5.6. Дерево префиксов довустввмх воарастают при удало- веночек схеки 8а.а (ш. Рве. 6.5) иии от корня, в бсуществует бесконечная допустимая цепочка, и схема Я не тотальна. Таким образом, частичный алгоритм распоапавания состоит в построении б по аадаиной схеме 8. Алгоритм сначала строит все префиксы длиные цепочек схемы н из инх выбирает префиксы допустимых цепочек, затем префик сы длины 2 и т. д. Для любого префикса конечной длины можно узнать, является ли он префиксом допустимой цепочки, т.
е. подтверждается лн он хотя бы одной свободной ивтерпретациев. (Если е — префикс недопустимой цепочки, то все префиксы цепочек, содержащие ет в качестве префикса, также недопустимы], Если схема Б тотальна, то дерево 6 конечно и па векотором шаге алгоритм закончит его построение, сообщив, что 8 тотальна. В противном случае он будет работать бесконечно долго, что и подтверждает частичную разрешимость проблемы тотальности стан дартных схем. ( ) 3.3. Проблема свободы. Т е о р е м а 5.4 (Патерсон).
Проблема свободы стандартных сж» не леллешел частично разрешимой. До к а за те л ь от в о. В гл. $ отмечалось, что проблема Поста ие разрешима, во частично разрепшма. Проблема, дополнительная к проблеме Поста, состоит в поиске алгоритма, который для любой системы Поста определял бы, пуста лк эта система, т. е. верно ли, что опа не имеет решений. Дополнительвав проблема Поста не является частично разрешимой, так кав в противном случае оказалась бы разрешимой основная проблема Поста (в силу теоремы 1Л). Покажем, что по заданной системе Поста можно построить стандартную схему, которая оказывается свободной тогда и только тогда, когда система Поста не имеет решений.
Пусть (Х, У) — система Поста иад алфавитом У, где Х =- = (а, аэ, ..., и„) и У = (Ц, рэ, ..., ()„) — наборы слов нз У», и > 2. Стандартная схема, соответствующая системе Поста (Х, У), показана на рис. 5.7. При построении схемы использованы три переменные х, у, х, одноместный функциональный символ / и символы ~ для каждого аб= У, одноместный предикатный символ р. Кроме того, если и = а а,аэ...
а„— слово иэ Уе, то через та (л) обозначим терм-выражение ( 1е,... ~ „л. Схема построена таким образом, что при произвольной свободной интерпретации значения переменных л и у накапливают термы-значения, соответствующие конкатенацням слов с одинаковыми индексами иэ Х и соответственно У. Схема не свободна только в том случае, если в некоторой программе (я, у) и моменту выполнения распоанавателя с меткой 4 (и + $) + $ значения л и у равны. В этом случае недопустимы цепочки, заканчивающиеся последовательностью ..., (4(п+ Ц+ $)', (4 (и+ Ц+ 2)е, 4 (и + 2). Однако такая ситуация (равенство значений л и у) возможна только тогда, когда система Поста (Х, У) имеет решение.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
