Гладкий - Формальные грамматики и языки - 1973 (947381), страница 55
Текст из файла (страница 55)
После этого читается граничный маркер и наступает заключительное состояние. Выполнение для М условия леммы 8.6 очевидно. Итак, лемма 8.5 доказана. Пусть теперь М вЂ” произвольная Э-машина. Обозначим через 444(М) множество записей всевозможных ситуаций М, через Я4(М) — множество записей всевозможных начальных ситуаций М и через Йа(М) — множе- ство записей всевозможных ситуаций М, имеющих вид (дб ~фх, ф, Л, ~у), где 4)! — заключительное состоя- ") Мы можем, разумеется, считать граничные маркеры М отлич.
иыми от 4Р. пРОБлемы, связАнные с Б.ГРАммАтикАми 273 еие М. Положим, кроме того, Р(М) =П(М) П [В!(М)()7(М))'Яа(М)[; иначе говоря, Р(М) — это множество протоколов тех вы- числений машины'М, с помощью которых значения аргу- мента вычисляемой ею функции ) переводятся в значе- ния самой 7'. Поскольку множество СЕР(М) (обозначе- ние Я введено на стр. 268) представимо в виде С Р(М) =И'(М)() С [)7, (М)(В(М))')7 (М)), а )44(М) и В»(М) суть А-языки, причем А-грамматики для них строятся очевидным образом, из только что до- казанной леммы непосредственно вытекает следующая Л е м м а 8.7. Для произвольной ДЭ-лгашины М лчно- жество СБР(М) есть линейный язык, и для всякой ДЭ-»гошины М можно построить линейную ОБ-гра»4- логику, порождающую С»Р(М).
Нам понадобится еще следующая простая конструк- ция. Пусть 6 = (д4, ..., й„, ...) — счетное множество символов и а, Ь вЂ” произвольные символы. Для каждой цепочки оз = 844, д! положим 4!, (оз,— Ы,=Ьа!+4!Ь ... ... Ьа'+'4Ь; кроме того, положим 2,(А) =ЬаЬ. Для каждого языка с в поонзвольном словаре, содержащемся в б, положим 74(Е) = (Л(оз) [оз ~ Ц. Мы можем допустить, что для каждой рассматриваемой нами Э-машины М соответствующий словарь Я содержится в б, и рассмот- реть язык Н(М) = 74(Р(М) ).
Имеет место Л ем м а 8.8. Для произвольного словаря )г, содер- жащего а и Ь, и для произвольной ДЭ-лгашины М мно- жество СГН(М) есть линейный язык, и для всякого словаря )г=» (а, Ь) и всякой ДЭ-машины М можно по- строить линейную ОБ-гралси вгику, порождающую Д о к а з а т е л ь с т в о.
Имеем С;Н (М) = С„()ь ( ) ) Х *() 0((),(Х))* — Н(М)). Поскольку 7,(Я) конечно, для пер- вого члена объединения по теореме 5А строится ОА-грамматика; второй член порождается линейной ОБ-грамматикой, схема которой получается из схемы соответствующей грамматики для СБР(М) заменой з к ж ом правиле каждого вхождения каждого основа д о 4+! ного символа й4 вхождением цепочки а пРОБлемы, сзяЗАнные с в-ГРАммАтикАми 276 в74 НЕРАЗРЕШИМЫЕ АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ [ГЛ. [ в <[ Теперь для некоторых инвариантных свойств ОВ грамматик легко доказать нераспознаваемость.
Т е о р е м а 8.4. Пусть )< — произвольный словарь содержащий не менее двух символов, Š— произвольно непустое множество натуральных чисел и осе — свойств язьша в словаре Р' иметь дополнение (до 1<'), число эле ментов которого конечно и является элементом Е. Тогд ' аг нераспознаваемо в классе линейных ОБ-граммати и тем более в классе всех ОБ-грамматик с основны словарем )<. Д о к а з а т е л ь с т в о. Для произвольной ДЭ-машин М мощность множества Н(М) равна мощности Р(М)> а эта последняя — мощности области определени вычисляемой данной машиной функции. Поэтому к проблеме распознавания ае сводится проблема распозг навания свойства машины М вычислять функцию *),область определения которой имеет конечную мощност являющуюся элементом Е.
Следствие[ 1. Следующие свойства языков не- распознаваемы в классе линейных (и тем более всех) ОБ-грамматик с заданным основным словарем мощности, большей или равной 2: а) иметь конечное дополнение; б) иметь дополнение, состоящее в точности из за данного. конечного числа элементов (в частности, пу стае) .. Действительно, для пункта а) достаточно взят в качестве Е множество всех натуральных чисел, дл пункта б) — множество, состоящее из одного числа. Следствие 2.
Не существует алгоритма, позволяющего для л<обой ОБ-грамматики (или даже для лю ' бой линейной ОВ-грамматики) с даннь<м основным словарем мощности, большей или равной 2, распознать, эквивалентна ли она заданной грамматике, порождаю. щей )>'. Тем более неразрешима общая проблема эквивалентности ОБ-грамматик.
Следствие 3. Не существует алгоритма, поэзо ляющего для любых двух ОБ-грамматик Г, и Гв с дан- *) Точнее следовало бы говорить о машинах с некоторым фнкснроввнным входным алфавитом н о проекции функции нв некоторыа фнкснроввнны» алфавит (ср. сноску нв стр. 264). ным основным словарем мощности, большей или равной 2, распознать, содержится ли Е(Г[) в Е(ГВ). В самом деле, по предыдущему следствию такой алгоритм невозможен даже для фиксированной грамматики Г<, если она порождает )< .
3 а м е ч а н и е. Ограничение на мощность словаря в теореме 8.4 и ее следствиях существенно (см. упражнение 8.16). Для доказательства нераспознаваемости ряда других свойств мы воспользуемся следующей теоремой. Теорем а 8.6. Пусть У, 1< — словари такие, чт<> У() 'Г< = 8, )[()<)) 2, и сг — класс ОБ-грамматик, содержащий все линейные ОБ-грамматики и такой, что соответствующий класс х'(У ) эффективно замкнут относительно объединения и относительно умножения слева на У* и справа на 1<'. Тогда всякое свойство языков, нетривиальное в м>(з' и), справедливое для У'1<* и сохраняющееся при операциях пересечения с А-языком и пРоектиРованиЯ, неРаспознаваемо в з ООР, ПРи этом сохранение свойства при проектировании может быть заменено более слабь<м требованием: если Е с= У*, ус= 1< и язык Еу обладает данным свойством, то им обладает и язык Е.
До к аз а тельство. Пусть сс — свойство языков, удовлетворяющее описанным условиям. В силу одного из этих условий должен существовать язык Ее~2'(т о), не обладающий свойством и. Для произвольного языка В~Я(У,) положим Е'= У'Е 0 Еор*. Если при этом Е = К', то Е' = У*)>*, так что и справедливо для Е'. Если же Е чь )<*, то, фиксировав цепочку у ен 1>* — Е и допустив, что свойство а имеет место для Е', получим ввиду условий, наложенных на а, что этим свойством должен обладать и язык Е' П У*у = Еву, а значит, и При(Еоу) = Ео, что неверно.
Таким образом, Е' обладает свойством сс тогда и только тогда, когда Е = )<". А это позволяет заключить, — поскольку Е' строится по Е эффективно, — что проблема распознавания совпадения языка класса 2'(9 Р) с У' сводится к проблеме распоЗванаиня а В КЛаССЕ сг О[)„. НО СВОйСтВО СОВПадатЬ С Рм нераспознаваемо в У Р (следствие 1 из теоремы 8А, пункт б)). 276 НЕРАЗРВШИМЫЕ АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ (ГЛ. В 4 Е 4( ПРОБЛЕМЫ, СВЯЗАННЫЕ С Б-ГРАММАТИКАМИ Е77 .
Следствие. Следующие свойства языков нераспознаваемы в классе ОБ-грамматик с заданным основным словарем мощности, большей или равной 4: (а) бь(ть однозначным Б-языком; (р) быть детермини рова(унь(м языком (т. е. допускаться детерминированной МП-машиной); (у) иметь бесконтекстное дополнение; (6) быть ОА-язьском; (е) быть линейным язь(ком; (~) быть металинейным языком; (т() быть итерационнолинейным языком; (О) быть ОАЕВ-языком.
Свойства (а) — (4() нераслознаваемы также в классе ОБ-ОАЕВ' грамматик, свойства (а) — (~) и (О) — в классе итерационно-линейных грамматик, свойства (а) — (Б) — в классе металинейных грамматик, свойства (а) — (6) — в клас. се линейны» грамматик (при том же ограничении на словарь). В самом деле, все перечисленнь4е классы грамматик дают классы язы4(ов, эффективно замкнутые относи тельно нужных опйраций (теорема 4.8, замечания н,, стр. 170, лемма 5.1); справедливость названных свойств для (7'()* очевидна, сохранение свойства (6) при нужных операциях обеспечивается теоремой 5.4, сохранение свойств (Б) †(О) — замечаниями 2 и 3 в копц О 5.4, нетривиальность свойств (а) — (О) в соответствую-; щих классах при (4((7) = 2 — примерами из О 4.4 (для (а) и (р) ), простой модификацией примера 2 из' $ 4.3*) (для у), примером к следствию из теоремы 5.7 (для (6)), примерами из упражнений 5.28, 5.28 (для (е) — (О)).
Свойства (а) и (5) при проектировании могут не сохраняться, но удовлетворяют указанному в конце формулировки теоремы 8.5 более слабому требованию (упражнение 4.35). То же верно, как нетрудно убедиться, для (у). Сохранение свойства (а) при пересечении с А-языком вытекает из упражнения 5.!7,а), свойства (5) — из теорем 5.5 и 5.3, свойства (у) — из теорем 4.8 и 5.4.
3 а м е ч а н и е. Утверждения следствия нз теоремы 8.5 справедливы для любого словаря мощности, большей илн равной 2 (упражнение 8.11). В случае одноэлементного словаря свойства (а) †(О) три. виальны. ') Именно, нужно убрать рнзлелнтель44ый символ Ь. Другие примеры нераспознаваемых в классе Б-грам ° матик свойств и отношений см. в упражнениях 8.12, 8.13, 8!5, 8.22. В заключение мы рассмотрим некоторые проблемы иного характера (второго из двух типов, указанных в й 8.1), а именно проблемы распознавания замещаемости, взаимозамещаемости и конфигураций. Мы покажем, что они неразрешимы уже для линейных языков; более того, для подходящих линейных языков неразрешимы и соответствующие частные проблемы.
Укажем способ построения этих языков. Пусть М— произвольная ДЭ-машина, в рабочем алфавите которой выделен символ ао такой, что все значения вычисляемой машиной М функции ! являются цепочками в (ао). Множество всех тех и, для которых а,", суть значения (, будем обозначать Ем. При надлежащем выборе М мы можем, очевидно„получить в качестве Ем произвольное рекурсивно перечислимое множество. Будем, кроме того, считать, что машина М имеет единственное заключительное состоЯние уы пРичем оно отлично от начального и пе встречается в левых частях инструкций; понятно, что класс множеств Ем при таком ограничении не сужается.
Положим далее Р' = (а, Ь) и построим по лемме 8.8 линейную ОБ-грамматику Гм, порождающую язык СРН(М). Рассмотрим произвольную цепочку 4о ее 7,(!Ге(М) ) (см. стр. 272, 273). Эта цепочка единственным образом представляется в следующем виде: !.(7о)Л(ЧЕ»47.-Ь)Х(4$)7.(у), где х и у — цепочки во входном и рабочем алфавитах М соответственно; обратно, всякая цепочка такого вида принадлежит Х()7е(М)). Обозначим через О4(М) и 9'(М) соответственно мно* жества всевозможных цепочек вида Х (4)о) Х (~ »47 ф У) с и Ь ~ Х (4~ х4(7 ф У) 74 (ф~) 74 (у) ЬЬ, где х, у — цепочки во входном и рабочем алфавитах М соответственно; й =]у[; с — символ, отличный от а и Ь.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
