1626435695-d1df5d2e6d953ce7ad4b4ccb5f4f4e30 (844296), страница 14
Текст из файла (страница 14)
Пусть М = = (и( и~ Рай рз (и) = 1), дз = п1ах рз (и). Это определение корректно, поскольку множество М конечно в непусто. Следовательвое ра (и) 4~ пз Отсюда следует Ус = (и ~ рз (и ) ~ Иг) а это множество конечно. ( ) С л е д с т в и е 3.2. 1Хрог)едрра рагногнагания гкгнеалгнт.ности длухлгнточнмх елен Бордо всегда еаканчиеается. Д о к а а а т е л ь с т в о. Пусть процедура распознавания применяется к двухленточнь(м схемам Берда (Р', и') н (Р", и').
Если не удается одна из первых двух операций (склеивание или уплотнение), то процедура распознавания, очевидно, заканчивается. Если же обе операции окааываются успешными, то применяется операция замыкания к диаграмме Р, которая получается вз исходных схем следуютцнм образом (здесь у', )", Н, р — морфнамы): )". Р' -а Р' + Р", )". Р" -а. Р' + Р, б:Р+Р" О, р:Р Р. Эти морфиамы таковы, что всякая вершина ибз Уи является либо образом некоторой вершины из Р' при морфиаме )'др, либо образом некоторой вершины из Р" при морфизме ("бр.
Предположим для определенности и = (у'др) (й), где й ~ Уи.. Тогда вершина и не может быть свободной, иначе свободной была бы аершвна и'. Следовательно, в Р нет свободных вершин, и операция замыкания, а тем самым процедура распознавания, заканчи-и Таким образом, процедура распознавания является алгорвтмом распознавания эквивалентности двухленточных схем Берда. Как показывает првмер на рис. 3.5, зто неверно для и-ленточных схем при н ~ 3. Задание 3.2. Варшаву и я-лгвточяой диаграммы яазоаем квазиполаой, если ш ($ ~ 1 ~ о) У) (з ~ ) ~ я, г Ч': )) еоршяаа о вмоет )-ааолодаяяов. Докажите, что опорацяя гамыяааяя закаачяааегоя пра оо прямояояяя я такам диаграммам, з которых аоо аоршяяы являются язазяполяымя, ф 3.
Двухгеловочные автоматы 3.1. Определения в пример. Дерхголоеочный агтааат А = = (У, ('), Б, дш ф-., г) имеет одну ленту и две головки, которые могут независимо перемещаться вдоль ленты в одном направлении. Множество состояний () = (~з () ()з разбито ва два непересекающихся подмножества; в состояниях из Д, активна первая головка, а в состояниях из ()з — вторая. Как и раньше, У здесь означает алфавит символов ва ленте, Н вЂ” множество заключительных состояний, Л с,"; (), до ~ (3 — начальное состояние, зО ф — «пустой» снмвол, а 1 — программа автомата А, т.
е. последовательность команд вида оа -»- д', где д, д' ~ Д, а Е= У, причем для любой пары (д, а) существует единственная команда, начинающаяся зтнмн символами. Двухголовочный автомат можно рассматривать как такой двухленточный автомат, который работает с идентичными словами на обеих лентах. На дзухголовочные автоматы естественным образом переносятся определения множества допускаемых слов, пустоты н эквивалентности. Несмотря на то, -что двухленточные н двухголовочние автоматм похожи друг на друга, нх свойства сильно отлнчаются. Так, проблема пустоты разрешима для многолевточных автоматов [$33) н неразрешима для многоголовочных ((35). Более того, в последнем случае она не является даже частично разрепшмой, в чем мы вскоре убедимся.
Проблема эквивалентности также не является частично разрешнмой для многоголовочных авто- о» матов, что легко доказывается»» сведением к ней проблемы пустоты. Однако, как доказано в предыдущем параграфе, проблема эквивалентности разрешима для двухленточных автоматов, н остается пока открытой для многоленточных автоматов с тремя н более левтамн. Приведем пример двухголовочного автомата, который прове- Рвс. 3.6. Доултолооочиый авторяет равенство двух последова- ' ' ' кот л тельно записанных слов в алфавите г' = (О, 1)'.
Признаком окончания каждого нз слов сделаем вспомогательный снмвол о, не входящий в У. Автомат должен допускать только слова ввда с» о а о, где а ~ г'о. Мы возьмем А= =(~'0 ( ). 0 0(3 ° Л я'„4~.1). где 0 =(Ь. И 4, дтт) — множество состояннй, в которых актнвна первая голов- 2»»» ка 0» = (йп дм д» д») — множество состояний, в которых активна вторая головка; я = (дтт) — множество, содержащее единственное заключительное состояние. Граф автомата показан на ркс. 3.6. На этом рисунке вместо многих »параллельных» дуг с разнымн пометкамн нарисована одна дуга со всеми зтнмн пометками.
Находясь в состоянии де, автомат передвигает первую головку 1 к началу второго слова и„обнаружив его, переходит в состояние б~~. Если конец ленты ~ встречается раньше символа е, автомат переходит в незаключительное состояние дбе. Если же автомат приходит к состоянию дг, он считывает поочередно символы вто- 1 рого слова первой головкой (состояние дг), а символы первого слова — второй головкой (состояния дгг и дгг), сравнивая зги символы. Автомат возвращается каждый раэ в состояние д~~, если символы одинаковы.
Если же обнаружится несовпадение символов или первая головка встречает конец слова раныпе символа е, автомат уходит в состояние дее. Попав в ато состояние, автомат не может выйти иэ него; перемещая вторую головку к концу слова на ленте, он достигает ф, находясь в неэаключнтельном состоянии, так что слово на ленте отвергается. Если первая головка достигнет конца второго слова, а вторая головка обнаружит, что первое слово тоже просмотрено до конца, то автомат перейдет в заключительное состояние о,. В противном случае автомат 1 перейдет в состояние бег, отвергая слово.
Этот пример легко обобщить на случай произвольного алфавита Г, увеличивая количество состояний множества (г. 3 а л а и и е З.З. Постройте деухгелевечпый автомат, которнй устапаэлпвает раеепстее пары слов е алфавите (О, Ц с точностью де перестапоепп некоторой единсгэеэпей пари еоселппх символов. 3.2. Проблемы пустоты н эквивалентности. В $ $ мы установили разрешимость проблемы эквивалентности одноленточных автоматов, выяснив предварительно, что разрешима проблема пустоты для этих автоматов.
Точно так же поступим при исследовании проблемы эквивалентности двухголовочных автоматов, но на этот раз сначала установим, что проблема пустоты не является частично разрешимой, а затем сведем ее к проблеме зквивапентностн. (В конце этого параграфа обсудим еще раз связь между этими двумя проблемами в более широком контексте).
Тот факт, что проблема пустоты двухголовочных автоматов не является частично раарешимой, установвм методом сведения, используя проблему зацикливания машин Тьюрннга. Будем говорить, что двуяголовочный автомат моделирует работу машины Тьюринга над некоторым начальным словом, если автомат допускает единственное слово — конечный протокол работы машины над ннм. Л е м м а 3.9 (Розенберг). Сугэвствувт алгоритм, нолюрмй для любой машини Тьюринга и для любого начального слова страши двухголовочнигг автомат, модвлируплиий вг работу над этим словом. Д о к а э а т е л ь с т в о.
Пусть задана машина Тьюринга Т = (вт, Ят, оет, ~г, !т) и слово а в алфавите Ут. Преобразуем программу гг таким образом, чтобы на каждом шаге машина могла выполнять только одно иэ следующих действий: сдвинуть головку влево; сдвинуть головку вправо; записать новый символ 62 мт ~11дач у» ...(команда ца дар)' 4 1).-. к.Р 'д Ъ о) ~ р я~~~'~уэ и.:вт р ~дан'~ уа ...(команда дп' дай)1 Ф 3)... ш р,'~ 1у зэ и «тр~пдл~узз .... (команда да- даг). 63 беэ сдвига головки. Это легко сделать, заменив каждую команду да-~-д'а'Н на дза команды: да-ч- д'а'р и д'а' -~- д'а'Н. Соседние конфигурации в протоколе машины, подаваемом на ленту автомата, будут разделены вспомогательным символом з ~ Ю Ут () От.
Он займет место между символом 4~т, ааключающим одну конфигурацию, н такам же символом, открывающим следующую. Конец протокола будет отмечатъся двумя звездочками. Алфавит моделирующего автомата представляет собой сумму множеств Уг, Чт н (Кт, з). Мы не будем составлять программу автомата во всех деталях. Вместо этого опишем структуру его программы н поведение автомата, выполняющего команды отделъных частей программы. В походном состоянии обе головки автомата обозревают, как обычно, первый символ заданного слова (т.
е. символ фт, начинающий протокол). Первая группа команд перемещает головку 1 на одну конфигурацию вперед, проверяя, имеет ли первая конфигурация вид Фтд,тифт, где а — начальное слово на ленте машины Т. Если это так, то начинает работу вторая группа команд, в противном случае — команды шестой группы, которые перемещают одну иэ головок на конец всего слова, поданного на ленту автомата, после чего автомат останавливается в незаключительком состоянни н слово иа ленте автомата отвергается. Вторая группа команд заставляет автомат поочередно перемещать головки, поторые сканируют рядом стоящие конфигурации и сравнивают их иа совпадение (см.
пример в п. 3 1). Заметим, что команды первых двух и шестой групп не зависят от программы машины Т, команды первой группы аавнсят от слова а. Если обе конфигурации просмотрены до конца и несовпадений не обнаружено, то это значит, что машина Тьюринга Т должна зациклнватъся, поэтому слово на ленте автомата не может быть конечным протоколом и должно быть отвергнуто. В этом случае начинают работать команды шестой (отвергающей) группы.
Если обнаружено несовпадение символов, стоящих на одинаковых по.зициях в соседних конфигурациях, применяются команды третьей или шестой группы. Команды третьей группы используются, если хотя бы один из несовпадающнх символов — символ состояяня иэ 9т, а команды шестой группы — в осталъвнх случаях. «Правильными» несовпадениями соседних конфигураций будем считать такие, которые возникают как результат применения команд из программы машины Т.
Эти несовпадения могут быть трех типов (р — совпадающие префиксы конфигураций, у — совпадающие суффиксы): Все три «правильных» несовпадения могут быть выделены реаервированием конечного числа состояний н подбором конечного числа команд автомата, вид которых зависит от программы машины Т. Эти команды организуют поочередный просмотр несовпадающих фрагментов двумя головками и выясняют, является ли несовпадение «правильным». Для тех читателей, которыевыполнили ааданне З.З, принцип подбора команд третьей группы понятен.
Если команды третьей группы обнаружили, что несовпадения «правильны», выполняются команды четвертой группы,провершощие совпадение суффиисов конфигураций. В противном случае начинают работу команды шестой группы. Четвертая группа команд похожа на вторую группу. Когда закончено сравнение двух соседних конфигураций, головка $ смещается вперед, и начинается сравнение следующей пары соседних конфигураций, для чего автомат переходит вновь ко второй группе команд. Если же головка 1 обнаружит два стоящих подряд символа е, предупреждающих о том, что головка просмотрела последнюю конфигурацию, автомат активизирует головку 2, задача которой — с помощью команд пятой группы убедиться, что это действительно заключительная конфигурация конечного протокола работы машины Т над словом а.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
