Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
ПРЕДВАРИТЕЛЬНЫЕ ЗАМЕЧАНИЯ
.253
можно, в силу тезиса Черча, точнее, «тезиса Тьюринга — Черча», понимать как ДЭ-машину, которая вычисляет функцию, определенную на всех цепочках Н заданного вида и принимающую на каждой из них значение, равное соответствующей цепочке Н. Впрочем, при доказательстве разрешимости алгоритмической проблемы обычно ограничиваются указанием принципа работы алгоритма, не приводя построения соответствующей машины Тьюринга (или рекурсивной схемы, нормального алгорифма и т. п.), поскольку такое построение, коль скоро алгоритм достаточно ясно описан, не представляет трудностей*), но при доказательстве неразрешимости необходимо устанавливать именно несуществование нужной машины Тьюринга (или эквивалентного механизма четко определенного вида, например рекурсивной схемы).
В предыдущем изложении мы неоднократно встречались с алгоритмическими проблемами, получавшими положительное решение. Сюда относятся все утверждения о возможности для всякой грамматики или машины некоторого специального вида построить эквивалентную грамматику или машину другого специального вида, о перестройке вывода и т. п. Напомним также об алгоритме, позволяющем по любой неукорачивающей грамматике Г и любой цепочке х в основном словаре этой грамматики распознать, принадлежит ли х языку L(T) (§ 3.3), и об алгоритмах для распознавания пустоты и конечности языка, порождаемого Б-грамматикой (§ 4.2). В настоящей же главе мы сосредоточим внимание на тех алгоритмических проблемах (касающихся грамматик), которые решаются отрицательно.
Проблемы, с которыми мы будем иметь дело, можно разделить на два типа. К первому типу принадлежат проблемы распознавания истинности предикатов, определенных на грамматиках. По большей части, но не всегда, речь будет идти об одноместных предикатах, т. е.
о свойствах грамматик; в случае многоместных предикатов естественно говорить об отношениях между
*) Возможны, вообще говоря, и неконструктивные доказательства существования алгоритма, не дающие способа его построить, например, путем приведения к противоречию утверждения о неразрешимости соответствующей проблемы.
*254 НЕРАЗРЕШИМЫЕ АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ [ГЛ.
грамматиками. Пусть — некоторый класс грамматики предикат Р(ГЬ ..., Г^) определен для всех Гь ...
..., Г„ е У. Мы будем называть предикат Р распознаваемым в классе если существует алгоритм, позволяющий для любых Ti, ..., распознать,
истинно ли утверждение Р(Гь ..., Г„), и нераспо-' знаваемым в классе 9~, если такого алгоритма нет., В частности, при п = 1 будем говорить о распознаваемом (нераспознаваемом) свойстве. Наибольший интерес представляют инвариантные свойства и отношения, т. е. такие свойства и отношения, которые зависят только от порождаемых грамматиками языков; иначе говоря, инвариантность предиката Р(Гь ..., Г„) означает, что из L(ri)=L(rO> ••• ..., L(Tn) = L(T'n) следует Р(Г„ ..., ГП)^Р(П, ...
Гп). Всякому инвариантному свойству грамматик, соответственно отношению между грамматиками, естественным образом сопоставляется некоторое свойство языков (отношение между языками). Если а — некоторое инвариантное свойство грамматик (отношение между грамматиками) и а' — соответствующее свойство-языков (отношение между языками), мы обычно будем вместо «а распознаваемо (нераспознаваемо) в классе гЬворить, что а' распознаваемо (нераспознаваемо) в том же классе. Так, результаты § 4.2 могут быть теперь сформулированы следующим образом: пустота и конечность языка распознаваемы в классе Б-грамматик.
Все свойства и отношения, нераспознаваемость которых будет доказываться в основном тексте этой главы, инвариантны. Примеры проблем, относящихся к распознаванию неинвариантных свойств и отношений, см. в упражнениях 8.1, 8.2, 8.15.
Если некоторое свойство или отношение распознаваемо в классе 0~, то оно, очевидно, распознаваемо и в любом классе, содержащемся в . Обратное, вообще говоря, неверно*); ниже мы увидим, например, что в
*) Однако если два класса грамматик «эффективно эквивалентны», т. е. для любой грамматики одного из этих классов можно построить эквивалентную грамматику другого класса, то из алгоритма, распознающего какое-либо инвариантное свойство в одном из этих классов, немедленно получается соответствующий алгоритм для другого (ср. общее замечание в конце настоящего параграфа).
ПРЕДВАРИТЕЛЬНЫЕ ЗАМЕЧАНИЯ
255
классе НС-грамматик пустота и конечность языка уже нераспознаваемы.
В дальнейшем нам будет полезен также следующий термин: мы будем называть свойство языков нетривиальным в некотором классе языков, если среди языков этого класса имеются как обладающие, так и не обладающие данным свойством.
Проблемы второго типа формулируются следующим образом. Пусть V — некоторый словарь, — класс грамматик и P(L, xlt ..., х„)—предикат, определенный для всех языков L, порождаемых грамматиками класса с основным словарем V, и всех цепочек Хи ..., хп е V*. Ставится вопрос: существует ли алгоритм, позволяющий по любой грамматике Г е 2Г с основным словарем V и любым п цепочкам х±, ..., хп ?= V* распознать, истинно ли утверждение P(L(T), хи ..., х„)? («Общая проблема распознавания Р в классе ».) Фиксировав грамматику Г° е 2Г с основным словарем V, можно поставить другой вопрос («проблему распознавания Р для Г°» или «частную проблему распознавания Р»): существует ли алгоритм, позволяющий по любым цепочкам хи ? ? ? , хп е V распознать, истинно ли P(L(T°), Xi, ..., х„)? Из неразрешимости частной проблемы распознавания Р хотя бы для одной грамматики класса У вытекает, очевидно, неразрешимость общей проблемы распознавания Р ъ {Г.
