Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
К этому типу относятся проблема распознавания принадлежности цепочки языку, порождаемому данной грамматикой, проблема распознавания замещаемости одной цепочки на другую в языке, порождаемом данной грамматикой, и т. п.
Заметим, что при фиксировании цепочек хи ,.., хп общая проблема распознавания P(L, Х\, хп) переходит в проблему первого типа — о распознавании некоторого свойства языков. Например, фиксируя х в предикате x е L, получаем проблему распознавания свойства языка содержать данную цепочку.
В заключение параграфа сделаем одно простое замечание, которое будет чрезвычайно полезно нам в дальнейшем. Пусть 91 и 33— классы конструктивных объектов, а — свойство объектов класса 91 и р — свойство объектов класса 33. Пусть, далее, имеется алгоритм
256 НЕРАЗРЕШИМЫЙ АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ [ГЛ. S
$, позволяющий для^ всякого а е 91 построить такое: Ь(а) е 33, что Ь(а) обладает свойством р тогда и толь* ко тогда, когда а обладает свойством а. Если при этом существует также алгоритм SR, позволяющий для всякого объекта b е 33 распознать, обладает ли он свойством Р, то есть и алгоритм, позволяющий для всякого объекта, а е 91 распознать, обладает ли он свойством а (достаточно по данному а построить Ь(а) и затем применить к Ь(а) алгоритм SR). Поэтому при наличии алгоритма; $ неразрешимость проблемы распознавания а влечет-неразрешимость проблемы распознавания р.
Если описанный алгоритм $ существует, мы бу-. дем говорить, что проблема распознавания а сводится к проблеме распознавания р.
Таким образом, для доказательства неразрешимости алгоритмической проблемы достаточно свести к ней какую-либо другую алгоритмическую проблему, неразрешимость которой уже доказана. Точнее, мы установили, это для проблем распознавания свойств; но тот же прием мы можем использовать и для проблем распознавания отношений, поскольку отношение, например, между двумя конструктивными объектами можно рассматривать как свойство упорядоченной пары объектов, а пара конструктивных объектов также есть конструктивный объект. :
§ 8.2. Инвариантные свойства произвольных грамматик
В дальнейшем нам часто придется, рассматривая некоторый класс грамматик выделять те грамматики» этого класса, которые имеют фиксированный основной-словарь V. Совокупность всех таких грамматик мы бу* дем обозначать через Ту, а класс языков, ими порож* даемых, — в соответствии с соглашением на стр. 30 — через 3? (2Г у). Напомним также, что класс произволь-; ных грамматик мы договорились обозначать через Г.
Целью настоящего параграфа является доказатель-' ство следующей теоремы.
Теорема 8.1. Каков бы ни был словарь V, никакое свойство языков, нетривиальное в классе 3? (Ту) — иначе говоря, в классе рекурсивно перечислимых язы->
§ 8.2] ИНВАРИАНТНЫЕ СВОЙСТВА ПРОИЗВОЛЬНЫХ ГРАММАТИК 257
ков, содержащихся в V*, — не может быть распознаваемым в классе Гу и тем более в классе всех грамматик.
Вместо этого утверждения нам удобнее будет доказывать другое, равносильное ему ввиду теоремы 1.4, а именно:
Теорема 8.Г. Каково бы ни было свойство языков а, нетривиальное в классе рекурсивно перечислимых языков, содержащихся в V*, где V — фиксированный непустой алфавит, не существует алгоритма, позволяющего для любой Э-машины М с входным алфавитом V распознать, обладает ли язык L(M) свойством а.
Для доказательства теоремы 8.1' установим, в свою очередь, справедливость следующей теоремы, которая понадобится нам и дальше.
Теорема 8.2 (теорема Райса). Пусть W и V — фиксированные непустые алфавиты и % — класс всевозможных частично рекурсивных функций, области определения и множества значений которых содержатся в W* и V* соответственно. Пусть, кроме того, а — произвольное свойство функций, нетривиальное в классе Ъ, т. е. такое, что в § есть как функции, обладающие этим свойством, так и функции, им не обладающие. Тогда не существует алгоритма, позволяющего для любой ДЭ-машины с входным алфавитом W распознать, обладает ли функция Пру/М, г&е f(x)—вычисляемая данной машиной функция *), свойством а.
Нетрудно видеть, что теорема 8.2 влечет теорему вЛ'. Действительно, по теоремам 1.2 и 1.3 для всякой
Э-машины М, допускающей L(M) s V*, можно построить ДЭ-машину М', вычисляющую функцию с множеством значений L(M). Область определения этой функции не обязана, вообще говоря, содержаться в W*, но она, во всяком случае, представляет собой язык в некотором (конечном) алфавите Z, и легко построить ДЭ-машину М" (см., например, упражнение 1.19, а), б)), осуществляющую взаимно однозначное отображение W* на Z*. Комбинируя машины М" и М', получаем ДЭ-машину Mi, вычисляющую функцию с множеством значений L(M) и областью определения, содержащейся в W*. С другой стороны, для любой Э-машины,
*) Очевидно, всякая ДЭ-машина вычисляет некоторую функцию (которая может, впрочем, оказаться нигде не определенной).
9 А. В. Гладкий
258 НЕРАЗРЕШИМЫЕ АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ [ГЛ. 8
вычисляющей функцию f(x), тривиальным образом строится Э-машина, вычисляющая функцию Пру/(х), а это ввиду теоремы 1.3 позволяет построить Э-машину (с входным алфавитом V), допускающую множество значений Пру/(х). Пусть теперь р— произвольное свойство языка и а — свойство функции иметь множество значений, проекция которого на V обладает свойством р. Из предыдущего ясно, что если р нетривиально в классе рекурсивно перечислимых языков в алфавите V, то а нетривиально в классе 3, и из существования алгоритма, распознающего по любой Э-машине М с входным алфавитом V, обладает ли L(M) свойством р, немедленно вытекало бы существование алгоритма, позволяющего по любой ДЭ-машине с входным алфавитом W распознать, обладает ли соответствующая функция Пру/(л:) свойством а.
