Гладкий - Формальные грамматики и языки - 1973 (947381), страница 54
Текст из файла (страница 54)
2бв ![еРАЗРешимые АлГОРитмические пРОБлемы [Гл, з 4 З4[ ПРОБЛЕМЫ, СВЯЗАННЫЕ С Б-ГРАММАТИКАМИ 2бэ свойство и р — наибольший из номеров цепочек х,..., хм то всякие два языка Т. и Ь', для которых имеет место равенство 1.П(о[1,..., сор) = 4.'П(ш1,..., [ор), либо оба обладают свойством Фе, либо оба не обладают. Но если 4) — наименьшее число, большее р и такое, что шеф ф1с "), то язык 1. =(Ы!,...,ш(а — 1))П1с не принадлежит Ы, в то время как Ь'= Т.Щш[)) ~,м, и при этом Т.П(ш1,..., шр) = Т.'П(ш1,..., шр). 8 8.4. Некоторые проблемы, связанные с Б-грамматиками При переходе от НС-грамматик к Б-грамматикам класс нераспознаваемых свойств языков сужается еще больше. Так, в классе Б-грамматик распознаваемы пустота (теорема 4.1), конечность (теорема 4.2), свойство содержать цепочку, содержащую вхождение х, или начинающуюся вхождением х, или оканчивающуюся таковым (упражнение 4.7); в классе НС-грамматик все эти свойства, как мы видели, нераспознаваемы.
Однако и для Б-грамматик можно доказать нераспознаваемость довольно обширного круга свойств. Этим, а также доказательством неразрешимости в классе Б-грамматик некоторых проблем иного типа мы сейчас и займемся. Впрочем, нам удобнее будет говорить не о Б-, а об ОБ- грамматиках (хотя все результаты останутся справедливыми и для Б-грамматик; соответствующие видоизменения конструкций очевидны, и упоминать о них мы не будем). Нам понадобится одно вспомогательное понятие, относящееся к машинам Тьюринга, и лемма, связывающая произвольные ДЭ-машины с ОБ-грамматиками. Пусть М вЂ” Э-машина с входным алфавитом У, рабочим алфавитом )Гг и множеством состояний [г.
Положим Х = У[))ьт[)[1()(К ф, ч), где 4[ — символ, не входящий в )г[)%1)ьг[)Щ, 4). Ситуацию (д„,х',х" Х',Х") машины М назовем п р а вил ь ной, если х'х" = ~хФ и Х'Хп = ф=Х для подходящих х ен $'", Х ~ [ьт~. 3 анисью правильной ситуации (до,х',х", Х', Х") бу- ") Если бы такого числа яе нашлось, то й имел бы конечное лополкекяе к, значит, был бы НС-языком.
дем называть цепочку ц„х'ЧхпХ'УХ". Для произвольного вычисления С = (Яо, 3[, ..., Я„) машины М будем называть его п р о т о к о л о м цепочку п(С) = 1(Бе) 1(8~) .. ... 1(5„), где 1(84) — запись ситуации 54. Множество всех протоколов машины М будем обозначать через П(М), дополнение П(М) до Х' — через П'(М).
Л ем м а 8.5. Для произвольной ДЭ-машины М множество П'(М) есть линейньсй язык, и для всякой ДЭ-машины М можно построить линейну[о ОБ-грамматику, порождаюи[ую П'(М). Предварительно докажем другую лемму. Л ем м а 8.6, Пусть Э-машина М имеет инструкции только типов (1) и (!Б) и для любой ее непустой входной цепочки х существует самое большее одно [х, у)-вычисление, причем это вычисление происходит в такой послгдоеательности: сначала читается символ цн на входной ленте, затем (если [х~ ) 1) — первь[й символ входной цепочки х, затем создается рабочая ячейка, и далее шаги типов (1) и (ш) чередуются через один, пока не будет прочитан последний символ цепочки х; после этого машина либо сразу останавливается, либо, прежде чем остановиться, делает еи!е о д и н и л и д в а шага типа (й!).
Пусть, кроме того, входной и рабочий алфавиты машина[ М представлены соответственно в виде )г= )г'() (т, [Р' = [)т'() )Р', где [г' П [Г = Ю" П [ьп = Я. Для произвольных двух языков (.4 ~ )ГФ", Т.з с: — В"(Р'" обозначим через Т (Т.ь Т.з) множество всевозможных цепочек ху таких, что хен (.4, уе= Тз и не существует [х,у]-вычисления машины М. Тогда для любых двух А-грамматик Г, и Гз таких, что Т. (Г[) с= У'17", Т.
(Гз) с: — [)т' Ф", можно построить линейную ОБ-грамматику, порождающую Т.м (1. (Г[), ЦГ )). Доказательство леммы 86. Поскольку для данной входной цепочки х самое большее при одном значении у, которое мы будем обозначать у(х), может существовать [х, у)-вычисление, ясно, что цепочка ху, где хен 4'.(Г,), уев 4.(Гз), принадлежит Т.м(1.(Г|),4.(Гз)) тогда и только тогда, когда выполняется одно из четырех условий: (а) цепочки у(х) не существует; (б) !у[( ()у(х) ); (в) [у)) (у(х) [; (г) существует такое 1= 1, ..., ш!п(!у), [у(х)1), что г-е слева символы цепочек у и у(х) различны.
Дизъюнкция этих условий ето неРАЭРешимые АлГОРитмические пРОБлемы ~гл. з ПРОБЛЕМЫ, СВЯЗАННЫЕ С Б-ГРАММАТИКАМИ 271 равносильна дизъюнкции (б') Ъ' (в') т«' (г'), где (б') = = (а) '/(б), (в ) = (а) ~/(Б), (г ) = (а) т«'(г). Иначе говоря, см(с.(Г1), 5(рз)) = 7-'()1»01-"', где 1.', с.", 7."'— множества цепочек хд, х ее 7.(Г1), у е Т.(Гз), удовлетворяющих (б'), (в') и (г') соответственно. Поэтому ввиду эффективной замкнутости класса линейных языков отБосительно объединения (стр. 170) нам достаточно указать способ построения линейных ОБ-грамматик для языков 7.', 7» и т'.м'.
В силу теорем 5.2 и 5.8 это равносильно построению однодорожечных МП-машин, допускающих указанные языки, по конечным автоматам М~ и Мь допускающим 1.(Г,) и 7.(Гз) соответственно. Машина М' для Т.' строится следующим образом: если на ее входной ленте записана цепочка ху, где Х~)Г'(7 ", у~ (Р"Мт *, тО СНаЧаЛа Оиа рабатаЕт На ВХОдНОй ленте, как Мь а на рабочей — как М; прочтя х, она начинает работать на входной ленте, как Мз, а на рабочей после каждого «входного» шага уничтожает одну ячейку; если после прочтения ху еще останутся рабочие ячейки, то машина уничтожает и их, после чего переходит в заключительное состояние; в противном случае после прочтения ху машина «ломается».
Машина М" для Т.м строится аналогично. Машина Мам для 7.»' работает так. Имея на входной ленте ху, где х ен )т'(7*, у ен Ж"07*, она сначала работает так же, как М', но потом, не дойдя до конца х, переходит «в другой режим»с на входной ленте продолжает работать так же, а на рабочей не делает ничего. При этом она «запоминает» тот символ Ь, который должна была бы записать на рабочей ленте машина М (или М') сразу после прочтения содержимого той входной ячейки, которую М"' обозревает к началу работы в новом режиме; пусть к этому времени рабочая лента состоит из т ячеек (возможно, 1= О) *).
Прочтя х, машина М"' снова начинает работать так же, как работала с этого момента М', пока не уничтожит всю рабочую ленту. Если к этому моменту входная цепочка будет прочитана целиком, машина ломается. В противном случае входная головка будет обозревать в данный момент 1+ 1-й слева символ цепочки у, и очередной шаг *) Разумеется, числа ~ машина «знать» не может. будет состоять в следующем как и на предыдущих ша гах, машина имитирует работу Мз, но одновременно проверяет, совпадает ли обозреваемый входной символ с запомненным ранее символом Ь'; если да — она ломается; если нет — продолжает работать просто как Мш и если у окажется «Мз-допущенной», переходит в заключительное состояние.
Доказательство леммы 85. Пусть Гà — множество записей всевозможных ситуаций данной ДЭ-машины М. Ясно, что Р есть А-язык; соответствующая А-грамматика строится без всякого труда. Обозначим через Т множество всевозможных цепочек вида ху, где х, у ~ )т и ситуация с записью у не является непосредственно достижимой из ситуации с запвсью х. Ввиду очевидного равенства П'(М) = Гт"Т)т' и Ся)т+, теоремы 5.4 и замечания на сгр. 170 нам достаточно построить линейную ОБ-грамматику, порождающую Т. Будем говорить, что инструкция Л' машины М применима к ситуации Я =(д,х',ах",Х',АХ«), если лева часть Л' содержит д и при этом: если Л' = с)Ь- д', то Ь = а, если Л' = Во- д', то В = А; если Л' = и- д'Л„ то Х'ФЛ; если Л'= с)- д'П, то Х" чьЛ.
Будем обозначать через т((Л') множество записей всевозможных ситуаций машины М, к которым применима инструкция Л', и через )Го — множество записей всевозможных ситуации М, к которым неприменимы никакие инструкции. Как )то, так и все )т(Л') являются А-языками, и построение соответствующих А-грамматик очевидно. П и этом Т = [Йо Й Т) () () [)т(Л') Й Т), где объединение берется по всем инструкциям М. Поскольку )то Й ри этом — о ЙТ= = )Го)Г, достаточно указать способ построения линейной Б-грамматики для каждого из языков )т(Л') Й Т. Ввиду детерминированности машины М к- каждой данной ситуации может быть применима только одна инструкция. Поэтому, если х ~)т(Л') и у ен )т, то ситуация Я' с записью у тогда и только тогда не является непосредственно достижимой из ситуации 5 с записью х, когда 8' не получается из Я применением инструкции Л'.
А отсюда по лемме 8.6 вытекает, что достаточно строить Э-машину М, удовлетворяющую условию этой леммы и такую, что для цепочек хон)т(Л») и тогда и только тогда существует [х, р)-вычисление 272 неРАБРешимые АлГОРитмические пРОБлемы [Гл. а машины М, когда ситуация с записью у получается из ситуации с записью х применением инструкции Л'. При этом возможны пять случаев, соответствующих возможным типам инструкций Л'. Ыы рассмотрим случай Л'= А!)- 4)', предоставив остальные (вполне аналогичные) читателю.
Машина М будет в этом случае, имея на входной ленте цепочку 4)х'Нх»Х'Вч!АХР (где в силу выбора типа инструкции А ен (ьт, В ен 4Р 0 ЦЦ), работать следующим образом. Сначала она читает 4) и пишет на рабочей ленте 4)'. Затем до прочтения В просто переписывает входные символы на рабочую ленту.
Прочтя В, она пишет на рабочей ленте ч!. (Подчеркнем, что это делается «недетерминированным образомтк машина может записать ч! после прочтения любого символа из Ф' 0 ЦЦ, но если в следующей входной ячейке не окажется Ч, то произойдет «поломка».) Затем, прочтя на входнои ленте Ч, она пишет на рабочей В. Далее, прочтя А, пишет на рабочей ленте символ, который на входной н4~осредственно следует за А (опять «недетер-. минированным образом»: символ пишется наугад, н в случае несовпадения его со следующим входным символом машина ломается). Далее, читая Х", машина после прочтения каждого символа пишет на рабочей ленте (как описано выше) тот символ, который на входной следует за прочитанным, а прочтя последний символ нз Х", переходит в специальное состояние 4) (если она, «не угадав», что данныи символ последнии, вместо перехода в д запишет что-нибудь на рабочей ленте, то на следующем шаге будет прочтен граничный маркер*) и произойдет поломка).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
