Гладкий - Формальные грамматики и языки - 1973 (947381), страница 50
Текст из файла (страница 50)
Оценить зависимость между активной ем- костью Г и высотой О. 7.8. Построить Б-грамматику, порождающую язык (а"Ь" [ л = 1, 2, ...)' и такую, что густоты деревьев выводов в ней не пре- восходят двух. 7.9. Показать, что если Б-грамматика Г обладает тем свойством, что для каждой цепочки нэ Е(Г) найдется дерево полного вывода в Г, густота которого не превосходит А, где А — постоянная, зави- сящая только от Г, то для Г можно построить эквивалентную ей Б-грамматику Г', в которой густоты всех деревьев выводов ограни- чены тем же числом й [Днковскнй 1972 (б)[.
7.10. а) Обобщить лемму 7,2 на случай произвольных Б-трам. матик. з б) 91зменить определение густоты так, чтобы лемма 7.2 (в фор- мулировке, приведенной в тексте) была справедлива для произволь- ных Б-грамматик. 7.!1. Показать, что активная емкость итерационно-линейной грам- матики не превосходит двух. Замечание. Вместе с упражнением 5,28 отсюда следует, что класс итерационно-линейных языков являетсн собственным подклас.
сом класса хх (Б). 7.12. Показать, что: а) класс ОАЕ-языков замкнут относительно усеченной итерации; б) ни один из классов Ы'ь(Б) относительно усеченвой итерации ! не замкнут. 713. Назовем грамматику контекстно-не укор а ч ива ю- щ е й, если каждое ее правило имеет енд хгру — ~-х'фу', где ы щ 820 [)82(и ий) 52; ф .8 ийг(уи'92) 9~и[А); х,у,х,»' у', [х[«.Х «~[я'[; [у[([у'[ (у и (р — соответственно основной и вспомога- тельный словари Г). Показать, что для любой контекстно-неукорачи- вающей ОАЕ-(ОАЕВ-) грамматики Г такой, что 1Г (а) (А, соответ.
ственно 1з(Г) ~А, можно построить эквивалевтную ей Б-ОАЕ-(ОАЕВ-) грамматику Г', также удовлетворящую условию 1Г (и) <~ й, соответственно 1з(Г') ( А [Диковский 1972 (6)). 7.14. Найти необходимое и достаточяое условие равенства нулю степе пени гнездования приведенной удлиняющей Б-грамматики. л и 7.15. Показать, что для функций ФГ(п) и ФГ (и) (стр- 84) имеют место аналоги теоремы 7.6. 7.16. Показать, что в любой Б-грамматике, порождающей иелнне н йный язык, из начального символа выводима цепочка, содержащая не менее двух вхождений самовставляющихся символов.
[Указали . э. Использовать упражнение 5.21, б).[ 7.17. Показать, что разброс любой однозначной Б-грамматики, порождающей нелинейный язык, мажорнрует подходящую линейную функцию. йвп пРедВАРительные ЗАмпчАния ГЛАВА 8 НЕРАЗРЕШИМЫЕ АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ $ 8.1. Предварительные замечания При изучении формальных грамматик, как и многих других математических объектов, нередко приходится сталкиваться с так называемыми массовыми проблемами.
Массовая проблема — это совокупность однотипных задач, связанных с конструктивными объектами некоторого четко определенного вида, причем каждая «индивидуальная» задача состоит в построении по заданному . объекту Е другого конструктивного объекта Н, имеющего,:.
вообще говоря, иной вид. В весьма распространенном частном случае требуется узнать, обладает ли Е некоторым свойртвом; тогда объект Н должен быть одной из двух конср(ант 1 и О (или, если угодно, «истина» и «ложь»), интерпретируемых как утверждения «Е обладает данным свойством» и «Е не обладает данным свойством» соответственно. Решение массовой проблемы ищется, как правило, в виде а л г о р и т м а, позволяющего для каждого объекта Е заданного вида построить соответствующий объект Н; поэтому массовые проблемы часто ' называют алгоритмическими.
Если нужный алгоритм существует, говорят, что данная алгоритмическая проблема разрешима, если нет — что она неразр е ш и м а. (Говорят также «проблема алгоритмически разрешима», соответственно «неразрешима».) В случае,, когда все Е и Н являются цепочками в некотором алфавите (или допускают эффективное кодирование с помощью цепочек, чтб имеет место в действительности для дюбых конструктивных объектов), требуемый алгоритм можно, в силу тезиса Черча,точнее, «тезиса Тьюринга— Черча», понимать как ДЭ-машину, которая вычисляет функцию, определенную на всех цепочках Е заданного вида и прини~иающую на каждой из них значение, равное соответствующей цепочке Н. Впрочем, при доказательстве разрешимости алгоритмической проблемы обычно ограничиваются указанием принципа работы алгоритма, не приводя построения соответствующей машины Тьюринга (или рекурсивной схемы, нормального алгорифма и т.
п.), поскольку такое построение, коль скоро алгоритм достаточно ясно описан, не представляет трудностей *), но при доказательстве неразрешимости необходимо устанавливать именно несуществование нужной машины Тьюринга (или эквивалентного механизма четко определенного вида, например рекурсивной схемы). В предыдущем изложении мы неоднократно встречались с алгоритмическими проблемами, получавшими положительное решение.
Сюда относятся все утверждения о возможности для всякой грамматики или машины некоторого специального вида построить эквивалентную грамматику или машину другого специального вида, о перестройке вывода и т. п. Напомним также об алгоритме, позволяющем по любой неукорачивающей грамматике Г и любой цепочке х в основном словаре этой грамматики распознать, принадлежит ли х языку 1.(Г) (ч З.З), и об алгоритмах для распознавания пустоты и конечности языка, порождаемого Б-грамматикой (5 4.2). В настоящей же главе мы сосредоточим внимание на тех алгоритмических проблемах (касающнхся грамматик), которые решаются отрицательно.
Проблемы, с которыми мы будем иметь дело, можно разделить на два типа. К первому типу принадлежат проблемы распознавания истинности предикатов, определенных на грамматиках. По большей части, но не всегда, речь будет идти об одноместных предикатах, т. е. о с во й с т в а х грамматик; в случае многоместных прер б ж ву "у в,, ства существования алгоритма, ие дающие способа его построить, иапример, иутем приведения и противоречию утверждения о вераврещимости соответствующей проблемы. НЕРАЗРЕШИМЫЕ АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ [ГЛ.
4 зл! ПРЕДВАРИТЕЛЬНЫЕ ЗАМЕЧАНИЯ «54 грамматиками. Пусть У вЂ” некоторый класс грамматик и предикат Р(ГБ ..., Г„) определен для всех Гь ... ..., Г„ен У. Мы будем называть предикат Р р а споз н а наем ы м в классе ~, если существует алгоритм, позволяющий для любых Гь ..., Г ~У распознать, истинно ли утверждение Р(Гь ..., Г„), и нераспо-. з н а наем ы м в классе У, если такого алгоритма нет. В частности, при п = 1 будем говорить о р а с пози аваемом (нераспознаваемом) свойстве. Наибольший интерес представляют и н в а р и а н т н ы е свойства и отношения, т.
е. такие свойства и отношения, которые зависят только от порождаемых грамматиками языков; иначе говоря, инвариантность предиката Р(ГО ..., Г ) означает, что из Т.(Г~) = Т,(Г',), ... ..., ь(Г„) = Ь(Г~) следует Р(Г„..., Г )= — Р(ГП ..., Г',). Всякому инвариантному свойству грамматик, соответственно отношению между грамматиками, естественным образом сопоставляется некоторое свойство языков (отношение между языками). Если св — некоторое инвариантное свойство грамматик (отиошение между грамматиками) и щ' — соответствующее свойство .
языков (отношенне между языками), мы обычно будем вместо «сх распознаваемо (нераспознаваемо) в классе У» пзворить, что а' распознаваемо (нераспознаваемо) в том же классе. Так, результаты ф 4.2 могут быть теперь сформулированы следующим образом: пустота и конечность языка распознаваемы в классе Б-грамматик. Все свойства и отношения, нераспознаваемость которых будет доказываться в основном тексте этой главы, инвариантны.
Примеры проблем, относящихся к распознаванию неинвариантных свойств и отношений, см. в упражнениях 8.1, 8.2, 8.15. Если некоторое свойство или отношение распознаваемо в классе У, то оно, очевидно, распознаваемо и в любом классе, содержащемся в У. Обратное, вообще говоря, неверно *); ниже мы увидим, например, что в э) Однако если двв класса грамматик «эффективно эквивалент. ны», т. е. для любой грамматики одного из этих классов мо»що построить эквиввлентную грамматику другого класса, то из алгоритма, рвспознвющего какое-либо инвариантное свойство в одном из этих классов, немедленно получается соответствующий алгоритм дли другого (ср.
общее звмечзиие в конце настоящего параграфа). классе НС-грамматик пустота и конечность языка уже нераспознаваемы. В дальнейшем нам будет полезен также следующий термин: мы будем называть свойство языков н етр ивиальным в некотором классе языков, если среди языков этого класса имеются как обладающие, так и не обладающие данным свойством. Проблемы второго типа формулируются следующим образом. Пусть (У вЂ” некоторый словарь, У вЂ” класс грамматик и Р(Т., хь ..., Лн) — предикат, определенный для всех языков Т., порождаемых грамматиками класса У с основным словарем )г, и всех цепочек хь ... , хн ее )У;. Ставится вопрос: существует ли алгоритм, позволяющий по любой грамматике ГееУ с основным словарем (г и любым п цепочкам хь ..., х ен )ге распознать, истинно ли утверждение Р(Е(Г), кь ..., х„)? («Общая проблема распознавания Р в классе У».) Фиксировав грамматику Ге ен У с основным словарем )У, можно поставить другой вопрос («проблему распознавания Р для Го» или «частную проблему распознавания Р»): существует ли алгоритм, позволяющий по любым цепочкам хь ..., к„ен 1' распознать, истинно ли Р(Е(Ге), х„..., х„)? Из неразрешимости частной проблемы распознавания Р хотя бы для одной грамматики класса У вытекает, очевидно, неразрешимость общей проблемы распознавания Р в У .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
