Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 94
Текст из файла (страница 94)
Для копирования состояния каждого МО и имитации одного перехода М используются пары из правила 3, а для копирования ленточных символов и при необходимости маркера №вЂ” из 2. Если М попадает в допускающее состояние, то с помощью пар из правила 4 и заключительной пары из 5 мы позволяем цепочке А догнать цепочку В, тем самым формируя решение. (г(ослгалгочиосшь) Нужно доказать, что если данный экземпляр МПСП имеет решевне, то только потому, что М допускает ге. Отметим, что, поскольку мы имеем дело с МПСП, любое решение должно начинаться с первой пары, так что начало частичного решения имеет следующий вид. А:№ В: №деге№ 9,4. ПРОБЛЕМА СООТВЕТСТВИЙ ПОСТА 411 Поскольку в этом частичном решении нет допускающего состояния, то пары из правил 4 и 5 бесполезны.
Состояния и окружающие их один или два символа могут быть обработаны только с помощью пар из правила 3, а все остальные ленточные символы и Ф должны быть обработаны с помощью пар из правила 2. Поэтому, если М не попала в допускающее состояние, все частичные решения имеют общий вид А:х В: ху, где х — последовательность МО машины М, представляющих вычисления М со входом эг, возможно, с символом Ф и началом а следующего МО в конце.
Разность у содержит завершение а, еще один символ я' и начало МО, следующего за а, вплоть до точки, на которой заканчивается а вх. Отметим, что до тех пор, пока М не попадает в допускающее состояние, частичное решение не является решением, поскольку цепочка В длиннее цепочки А.
Поэтому, если решение существует, то М должна когда-нибудь попасть в допускающее состояние, т.е. допустить и. П 9.4.4. Чпражнення к разделу 9.4 9.4.1. Выясните, имеют ли решение следующие экземгпяры ПСП. Каждый из них представлен двумя списками — А и В, и 1-е цепочки списков соответствуют друг другу (! = 1, 2, ...). а) (я)А =(01,001,10);В=(011,10,00). б) А =(01,001, 10); В=(011,01,00). в) А = (аЬ, а, Ьс, с); В = (Ьс, аЬ, са, а).
(!) Было доказано, что ПСП неразрешима в предположении, что алфавит Х может быть произвольным. Покажите, что ПСП неразрешима даже при ограничении Х = (О, 1), сведя ПСП к данному частному случаю. 9.4.3. (е!) Допустим, ПСП ограничена односимвольным алфавитом Х = (О), Будет ли ПСП и в этом ограниченном случае по-прежнему неразрешимой? 9.4.4. (!) ГАГ-система Поста образуется множеством пар цепочек в некотором конечном алфавите Х и стартовой цепочкой.
Если (и, х) — пара и у — произвольная цепочка в Х, то мы говорим, что згу 1- ух. Таким образом, на одном шаге можно стереть некоторый префикс и "текущей" цепочки ну и вместо него в конце приписать второй компонент пары с н — цепочку х. Определим )- как нуль или несколько шагов 1-, точно так же, как для порождений в КС-грам- матиках. Покажите, что проблема выяснения, верно ли х )- в для данного мно- жества пар Р и стартовой цепочки х, неразрешима.
Указание. Пусть для любых ГЛАВА 9. НЕРАЗРЕШИМОСТЬ 412 МТ М и цепочки и стартовая цепочка з является начальным МО со входом зг и разделителем Ф на конце. Выберите пары Р так, что всякое МО М должно в конце концов превращаться в МО, в которое М попадает за один переход. Устройте так, что если М попадает в допускающее состояние, то текущая цепочка может быть в конце концов стерта, т.е. сведена к е 9.5. Другие неразрешимые проблемы Здесь рассматривается ряд других неразрешигиых проблем. Основным методом докамтельства их неразрешимости является сведение к ним ПСП. 9.5.1.
Проблемы, связанные с программами Прежде всего, отметим, что на любом привычном языке можно написать программу, которая на вход получает экземпляр ПСП и ищет решение по определенной системе, например, в порядке возрастания длины (числа пар) потенциальных решений. Поскольку ПСП может иметь произвольный алфавит, нужно закодировать символы ее алфавита с вомошью двоичного или другого фиксированного алфавита, о чем говорилось во врезке "ПСП как язык" в разделе 9.4.1. Наша программа может выполнять любое конкретное действие, например, останавливаться или печатать фразу )те11о, мог1д, если она нашла решение. В противном случае программа никогда не выполняет это конкретное действие. Таким образом, вопрес о том, печатает ли программа пе11о, мог1с1, останавливается ли, вызывает ли определенную функцию, заставляет ли консоль звенеть, или выполняет любое другое нетривиальное действие, неразрешим.
В действительности для программ справедлив аналог теоремы Райса: всякое нетривиальное свойство программы, связанное с ее действиями (ио не лексическое или синтаксическое свойство самой программы), является нераз- лжлямюм. 9.5.2. Неразрешимость проблемы неоднозначности КС-грамматик Программы и машины Тьюринга — это в общем-то одно и то же, так что в замечаниях ю раздела 9.5.! нет ничего удивительного.
Теперь мы увидим, как ПСП можно свести к проблеме, которая, на первый взгляд, совсем не похожа на вопрос о компьютерах. Это проблема выяснения, является ли данная КС-грамматика неоднозначной. Основная идея заключается в рассмозрении цепочек, представляющих обращение последовательности индексов, вместе с соответствующими им цепочками одного из списков экземпляра ПСП. Такие цепочки могут порождаться некоторой грамматикой. Аналогичное множество цепочек для второго списка экземпляра ПСП также может порождаться некоторой грамматикой.
Если объединить эти грамматики очевидным способом, то найдется цепочка, которая порождается правилами каждой исходной грамматики тогда и только тогда, 9.5. ДРУГИЕ НЕРАЗРЕШИМЫЕ ПРОБЛЕМЫ 413 когда данный экземпляр ПСП имеет решение. Таким образом, решение существует тогда и только тогда, когда в грамматике для объединения присутствует неоднозначность. Уточним эту идею. Пусть экземпляр ПСП состоит из списков А = тин тиз, ..., тек и В = хь хз, ..., хн Для списка А построим КС-грамматику с одной переменной А. Терминалами будут все символы алфавита Х, используемые в данном экземпляре ПСП, плюс не пересекаюшееся с Х множество индексных символов аь аз, ..., аь которые представляют выборы пар цепочек в решении ПСП.
Таким образом, индексный символ а, представляет выбор из из списка А или х, из списка В. Продукции КС-грамматики для списка А имеют следуюший вид. А — ь и,Аа, ~ зизАаз ~ ... ~ ти„Ааи ~ иза~ ~ и таз ~ .. ! теьаь Обозначим эту грамматику через Ом а ее язык — через Т.м Язык типа Ех будет называть- ся в дальнейшем языком для списка А. Заметим, что все терминальные цепочки, порожденные переменной А в 0„, имеют вид тенте„" и, а, ".апач при некотором пз й 1, где ть зз, ..., з' — последовательность целых чисел в пределах от 1 до 1г.
Все выводимые цепочки содержат одиночный символ А, отделяющий цепочки и от индексных символов а, до тех пор, пока не используется одно из Й правил последней группы, в которых А отсутствует. Поэтому деревья разбора имеют структуру, представленную на рис. 9.16. А Ю 2 а,. 2 Ю ° и Рис. 9.!6 Общий вид деревьев разбора в граииатике Ол Заметим также, что любая терминальная цепочка порождается в 6ь одним-единственным способом. Индексные символы в конце цепочки однозначно определяют, ка- кое именно правило должно использоваться на каждом шаге, поскольку тела лишь двух ГЛАВА 9.
НЕРАЗРЕШИМОСТЬ 414 продукций оканчиваются данным индексным символом а;: А — э и;Аа, и А — э и;аь Первую продукцию нужно использовать, когда данный шаг порождения не последний, в против- ком же случае используется вторая продукция. Рассмотрим теперь вторую часть экземпляра ПСП вЂ” список В =х,,хь ...,хь Этому списку мы поставим в соответствие еще одну грамматику Ов с такими про- дукциями. В -+ х,Ва, ! хзВаз ~ ... ~ хиВае! х~я~ ! Хзпз! ... ! хейг язык этой грамматики обозначим через 2в. Все замечания, касающиеся Ом справедливы в для Ов. В частности, терминальная цепочка из ьв имеет одно-единственное порождекке, определяемое индексными символами в конце этой цепочки.
Наконец, мы объединяем языки и грамматики двух списков, формируя грамматику бхв для всего данного экземпляра ПСП. Олв имеет следующие компоненты. 1. Переменные А, В и Я, последняя из которых — стартовый символ. 2. Продукции 5-+ А ~ В. 3. Все продукции грамматики Оь. 4. Все продукции грамматики Ов.
Утверждаем, что грамматика Оьв неоднозначна тогда и только тогда„когда экземпляр (А, В) ПСП имеет решение. Это утверждение является основным в следующей теореме. Теорема 9.20. Вопрос о неоднозначности КС-грамматики неразрешим. Основная часть сведения ПСП к вопросу о неразрешимости КС-грамматики щюведеяа выше. В силу неразрешимости ПСП это сведение доказывает неразрешимость проблемы неоднозначности КС-грамматики. Остается лишь показать корректность приве- Ленной конструкции, т.е. что ° Одв неоднозначна тогда и только тогда, когда экземпляр (А, В) ПСП имеет решение.
(Досваночносгяь) Предположим, что гь (ь ...,1 — решение данного экземпляра ПСП. Рассмотрим два порождения в Охв. 5 ~ А =э и'чА оп =э нгцю;,Аа; ао — -з кцгга" в,,Аа;„и апач ~ визга" Иыа, " аоал 5 =» В =э хаВач =эхчхцВаоач =э ". =ь хчха."х,,Ва," ааач =эхчхе" х,„а; чааач Поскольку й, (ъ ..., 1 — решение, то и яиц".ж, = хпх„" х,„, т.е, эти два порождения представляют собой порождения одной и той же цепочки.
А поскольку сами порожде- 9.5. ДРУГИЕ НЕРАЗРЕШИМЫЕ ПРОБЛЕМЫ ния, очевидно, являются двумя различными левыми порождениями одной и той же терминальной цепочки, делаем вывод, что грамматика сгАв неоднозначна. (Необходиносмь) Как было отмечено ранее, для данной терминальной цепочки существует не более одного порождения в бя и не более одного порождения в Ов.
Поэтому терминальная цепочка может иметь в б„в даа левых порождения лишь в том случае, если одно из них начинается с Я =э А и продолжается порождением в бм а второе начинается с Я =~ В и продолжается порождением в Ов. Цепочка с двумя порождениями имеет окончание из индексов а; " аоа„при некотором т > Е Это окончание и должно быть решением данного экземпляра ПСП, поскольку то, что ей предшествует в цепочке с двумя порождениями, есть одновременно и нз1жо' 'н и х>~хе х| Г~2 9.5.3. Дополнение языка списка Наличие контекстно-свободных языков, подобных 1,А для списка А, позволяет пока- зать неразрешимость ряла проблем, связанных с КС-языками. Еше больше фактов о неразрешимости свойств КС-языков можно получить, рассмотрев дополнение этого языка 1, .
Отметим, что язык Е, состоит из всех цепочек в алфавите Х О (аз, а,, ..., аь), не содержащихся в Вм где Х вЂ” алфавит некоторого экземпляра ПСП, а а, — символы, которые не принадлежат Х и представляют индексы пар в этом экземппяре ПСП. Интересными элементами языка Е, являются цепочки, префикс которых принадлежит Х, т.е. является конкатенацией цепочек из списка А, а суффикс состоит из индексных символов, ле соответствующих цепочкам из префикса. Однако помимо этих элементов в 1„содержатся цепочки неправильного вида, не принадлежащие языку регулярного выражения Х (аз '- аэ -> ... ь аь) .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
