Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
УПРАЖНЕНИЯ
27?
L(I\) с результирующим с; в) замещаема ли цепочка bbbb на х относительно L(Ti); г) замещаема ли х на baab относительно ?(Гг); д) являются ли х и bbbb вза-имозамещаемыми относительно L (П).
По поводу возможности уменьшить здесь мощности словарей см. упражнения 8.19 и 8.20, по поводу распознавания конфигураций высших рангов — упражнение 8.21.
Упражнения
8.1. Закодировав всевозможные грамматики, как в доказательстве теоремы 2.4, назовем грамматику Г самопорож дающей, если наименьший (в лексикографическом порядке) из ее кодов принадлежит ?(Г). Показать, что самопорождаемость нераспознаваема в классе Г *). [Указание. Показать, что множество наименьших кодов несамопорождающих грамматик не порождается никакой грамматикой.]
8.2. Показать, что следующие свойства грамматик нераспозна-, ваемы в классе Г:
а) иметь ограниченное растяжение (т. е. емкость, мажорируемую линейной функцией);
б) быть грамматикой без растяжения.
8.3. Можно ли перенести результат упражнения 8.1 на класс НС?
8.4. а) Пусть L0^~ произвольный НС-язык, L — произвольный непустой НС-язык и 2? — класс языков, содержащий L0 U L и не содержащий ни одного языка вида L0 U (L — {*}), где *eL Показать, что свойство принадлежать S’ нераспознаваемо в классе НС.
б) То же с заменой языков L — {*} на языки вида L — L', где L' — непустое конечное подмножество L.
8.5. Показать, что в классе НС нераспознаваемо свойство принадлежать 9?тп (НС).
8.6. Язык L в словаре V имеет нетривиальную заме-Щаемость, если найдется хотя бы одна пара цепочек х, у е V*, х Ф у, такая, что х является подцепочкой некоторой цепочки из L и при этом х =ф у. Показать, что свойство иметь нетривиальную заме-
v. L
щаемость нераспознаваемо в классе НС.
8.7. Усилить лемму 8.1 и теорему 8.2, показав, что следующие множества не могут быть рекурсивно перечислимыми:
а) множество кодов несамоприменимых Э-машин;
б) множество кодов таких ДЭ-машин, что вычисляемые ими Функции обладают некоторым свойством, справедливым для нигде че определенной функции, но не для всех частично рекурсивных Функций.
8.8. Используя упражнение 8.7,6), показать, что следующие множества не могут быть рекурсивно перечислимыми:
*) Г — класс всех грамматик (стр. 30),
280 НЕРАЗРЕШИМЫЕ АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ [ГЛ. 8
а) множество кодов грамматик, обладающих некоторым инвариантным и нетривиальным в классе Г свойством, справедливым для грамматик, порождающих пустой язык;
б) множество кодов НС-грамматик, для которых порождаемые ' ими языки принадлежат некоторому классу, удовлетворяющему уело* вию леммы 8.4 или теоремы 8.3 (но не дополнение к такому множеству!).
8.9. Назовем свойство языков в словаре V «булевски перечисли- , мым», если оно представимо в виде BijV... VSifeV-.-, где Вt — булевы свойства, занумерованные с помощью некоторого эффективно- ; го кодирования булевых выражений (от переменных XIt ..., Хп ..., где Хп означает «еле L»; соп — цепочка с номером п, см. стр. 267),
и {ii, ik, • • — рекурсивно перечислимое множество натуральных
чисел. Показать, что если Э~ — класс грамматик такой, что соответствующий класс & (?Г) содержит вместе с каждым конечным языком все его НС-надъязыки и множество кодов НС-грамматик из ?Г рекурсив- -но перечислимо, то свойство быть НС-языком, принадлежащим i?(?r), булевски перечислимо. [Указание. Использовать упражнение 8.8, б).J
8.10. Опираясь непосредственно на лемму 8.8, доказать, что в ; классе линейных языков нераспознаваемы свойства быть ОА-языком " и иметь бесконтекстное дополнений
8.11. Показать, что все результаты следствия из теоремы 8.5 справедливы для любого словаря мощности, большей или равной 2. [Указание. Установить сводимость проблем распознавания свойств' (а) •— (0) для словаря мощности 4 к соответствующим проблемам ? для словаря мощности 2.]
8.12. Доказать нераспозиаваемость в классе Бу, где V — словарь мощности, большей или равной 2, следующих свойств языков:
а) порождаться Б-грамматикой, активная емкость которой не-превышает заданного числа k\
б) быть ОАЕ-языком;
в) удовлетворять условию х =%> у, где х и у — произвольные
vZl
фиксированные различные цепочки в V;
г) иметь заданную конфигурацию заданного ранга с заданным
результирующим; "
д) содержать бесконечный ОА-язык [Ginsburg 1966, лемма 4.3.4].
8.13. Доказать нераспозиаваемость в классе Бу, где V — словарь мощности, большей или равной 2, следующих отношений между языками Ц и L2:
а) пустоты пересечения L\ Г) L%\
б) бесконтекстности пересечения L\ Г) L2;
в) существования конечного автомата с выходом (упражне-ние 5.8), переводящего Li в бесконечное подмножество L2 [Ginsburg; 1966, теорема 4.3.2].
8.14. Доказать, что для словаря V мощности, большей или равной 2, невозможен алгоритм, позволяющий для любых двух систем п цепочек х,, ..., хп и уи .,., уп в V узнать, существует ли' такая\ (непустая) последовательность чисел h, ..., i* (i'i, ..., ih = s = 1, •. •, n), что Xit ... x-,k = yix... yik (теорема Поста о проблеме соответствий; см. [Post 1946. Марков 1954]).
УПРАЖНЕНИЯ
281
