Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
б) Аналогично для Хг(п).
Упражнения
7.1. а) Показать, что левая глубина и разброс любой Б-грамматики, порождающей язык Дика, мажорируют подходящие линейные функции.
б) То же для скобочного языка.
7.2. Показать, что левая глубина любой однозначной . Б-грам-матики, порождающей неавтоматный язык, мажорирует подходящую линейную функцию.
7.3. Показать, что для произвольных Б-грамматик и Г2 можно
построить Б-грамматик'у Г, порождающую язык (Гi) Z. (Г2) и такую, что Dr («) < max (п), (п) )•
7.4. Определим «центральную глубину» и «краевую глубину» цепочки соё (VU W)+ соответственно как наименьшее значение левой и правой глубины со и как наименьшее число п, для которого ш представима в виде со^соз, где х ^ V* ц |wi| + |cp2| = п. Далее обычным способом определим центральную и краевую глубину грамматики.
250
СЛОЖНОСТЬ ВЫВОДА В Б-ГРАММАТИК АХ
[ГЛ. 7
Показать, что для центральной и краевой глубины справедливы аналоги теоремы 7.2.
7.5. а) Показать, что для любой НС-грамматики Г и любого действительного числа с, 0 < с < 1, можно построить НС-грамма-тику Г', эквивалентную Г и такую, что (п) ^ сп.
б) Можно ли распространить на случай произвольных НС-грам-Матик теорему 7.4?
7.6. Показать, что для любого k= 1, 2,... и любого l = k+ 1,
k -+- 2, ... можно построить такую Б-грамматику Г, что L (Г) е s &k+i (Б) — №) и при этом /о(Г) = I.
7.7. а) Показать, что если h — высота дерева подчинения, согласованного с некоторой системой составляющих густоты р, (т. е. такой, что густота соответствующего дерева составляющих равна ц), то ц ^ ft.
б) Показать, что для Б-грамматики Г тогда и только тогда существует (и может быть построена) сильно (соответственно слабо) эквивалентная ей Д-грамматика О ограниченной высоты, когда активная емкость Г ограничена константой (соответственно ?(Г) является ОАЕ-языком). Оценить зависимость меж_ду активной емкостью Г и высотой G.
7.8. Построить Б-грамматику, порождающую язык [апЬп | п = = 1, 2, .. .}? и такую, что густоты деревьев выводов в ней не превосходят двух.
7.9. Показать, что если Б-грамматика Г обладает тем свойством, что для каждой цепочки из /.(Г) найдется дерево полного вывода в Г, густота которого не превосходит к, где к — постоянная, зависящая только от Г, то для Г можно построить эквивалентную ей Б-грамматику Г', в которой густоты всех деревьев выводов ограничены тем же числом k [Диковский 1972 (б)].
7.10. а) Обобщить лемму 7.2 на случай произвольных Б-грамматик. ,
б) Изменить определение густоты так, чтобы лемма 7.2 (в формулировке, приведенной в тексте) была справедлива для произвольных Б-грамматик.
7.11. Показать, что активная емкость итерационно-линейной грамматики не превосходит двух.
Замечание. Вместе с упражнением 5.28 отсюда следует, что класс итерационно-линейных языков является собственным подклассом класса (Б).
7.12. Показать, что:
а) класс ОАЕ-языков замкнут относительно усеченной итерации;
б) ни один из классов .2^ (Б) относительно усеченной итерации не замкнут.
7.13. Назовем грамматику контекстно-неукорачива го-щей, если каждое ее правило имеет иид xwu x'ibi/' где w е W U U W(VU W)*W; t|>gsTPU1F(VU1F)*1FU{A}; х, у, х', у' е [/*; |*|<
МОЛ (V и R7 — соответственно основной и вспомогательный словари Г). Показать, что для любой кочтекстно-неукорачи-вающей ОАЕ-(ОАЕВ-) грамматики Г такой, что Ir(n)^k, соответственно /о(Г) sg:fe, можно построить эквивалентную ей Б-ОАЕ-(ОАЕВ-)
УПРАЖНЕНИЯ
251
грамматику Г', также удовлетворящую условию Iг' («) ^ к, соответственно /о(Г') к [Диковский 1972 (б)].
7.14. Найти необходимое и достаточное условие равенства нулю степени гнездования приведенной удлиняющей Б-грамматики.
7.15. Показать, что для функций (я) и CDjJ (п) (стр. 84)
имеют место аналоги теоремы 7.6.
7.16. Показать, что в любой Б-грамматике, порождающей нелинейный язык, из начального символа выводима цепочка, содержащая не менее двух вхождений самовставляющихся символов. [Указание. Использовать упражнение 5.21,6).]
7.17. Показать, что разброс любой однозначной Б-грамматики, порождающей нелинейный язык, мажорирует подходящую линейную функцию.
ГЛАВА 8
НЕРАЗРЕШИМЫЕ АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ
§ 8.1. Предварительные замечания
При изучении формальных грамматик, как и многих других математических объектов, нередко приходится сталкиваться с так называемыми массовыми проблемами. Массовая проблема — это совокупность однотипных задач, связанных с конструктивными объектами некоторого четко определенного вида, причем каждая «индивидуальная» задача состоит в построении по заданному • объекту S другого конструктивного объекта Н, имеющего, вообще говоря, иной вид. В весьма распространенном частном случае требуется узнать, обладает ли Е некоторым свойством; тогда объект Н должен быть одной из двух констант 1 и 0 (или, если угодно, «истина» и «ложь»), ’ интерпретируемых как утверждения «Е обладает данным свойством» и «Е не обладает данным свойством» соответственно. Решение массовой проблемы ищется, как правило, в виде алгоритма, позволяющего для каждого объекта Е заданного вида построить соответствующий объект Н; поэтому массовые проблемы часто называют алгоритмическими. Если нужный алгоритм существует, говорят, что данная алгоритмическая проблема разрешима, если нет — что она неразрешима. (Говорят также «проблема алгоритмически разрешима», соответственно «неразрешима».) В случае, когда все Е и Н являются цепочками в некотором алфавите (или допускают эффективное кодирование с помощью цепочек, что имеет место в действительности для любых конструктивных объектов), требуемый алгоритм
