Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
3.1. Построить дерево вывода и растянутое дерево вывода цепочки ЬакЬ в грамматике примера 1 из § 3.4.
3.2. Показать, что одному размеченному выводу в НС-грамма-тике Г может отвечать более одного растянутого дерева вывода тогда и только тогда, когда схема Г содержит правило вида фЛ (|т|)п|бг|)-*? фЛ (|г|)nfAgS\|), где А, В — вспомогательные символы, г| Ф Л, п = 0, 1, ..., k = 1, 2, ..., причем левая часть этого правила входит хотя бы в одну цепочку, выводимую из какого-либо вспомогательного символа.
3.3. Показать, что для всякого сжатого дерева вывода Т в НС-грамматике Г найдется такой бесповторный размеченный вывод D в Г, что одио из сжатых деревьев, отвечающих D, совпадает с Т.
3.4. Подсчитать число деревьев вывода и сжатых деревьев вывода цепочки азпЬзп в грамматике со схемой {I А, I В, А -> аАЬ, А -> ab, В -> а3ВЬ, В аВЬ3, В -» а3Ь, В ab3}.
3.5. а) Показать, что для. каждой НС-грамматики Г имеет место неравенство ^ 'Уг («) + d, где d—максимум длин цепочек
112
ГРАММАТИКИ СОСТАВЛЯЮЩИХ
[ГЛ. 3
х в основном словаре Г, для которых существуют правила Г, имеющие вид -> q>*0i|). Аналогично для ^р и Yp.
б) Построить НС-грамматику Г такую, что Yp (п) =*> 1, °ул (п)—п.
3.6. Построить неукорачивающие или почти неукорачивающие грамматики, порождающие следующие языки:
а) [хх | а: «= {о,.а*}+};
б) (а"а2 ... а?[я = 1, 2, ...J (к — фиксированное натуральное число);
в) {anbmanbm | т., ге= 1, 2, ...};
г) {* | х е {а,....ак, 6,..bk)+; \х\а_ = \х Ц (г = 1,..., k)\,
д) множество всех простых чисел в простейшей записи;
е) {х * у * г | ху = г], где х, у, г — двоичные записи натуральных чисел х, у, г соответственно.
3.7. Коммутативным замыканием языка L s
s {aJt ..., называется язык | х е {a^ — &3у (у е
е L & | х \at — | у |а., i=l..fej. Показать, что:
а) коммутативное замыкание НС-языка есть НС-язык (причем по любой НС-грамматике Г можно построить НС-грамматику, порождающую коммутативное замыкание ?(Г));
б) обратное неверно (более того, даже неперечислимый язык может иметь в качестве коммутативного замыкания язык {а1; Лг}*).
3.8. Показать, что для любой НС-грамматики можно построить эквивалентную ей грамматику без растяжения, не являющуюся почти неукорачивающей.
3.9. Показать, что для любой НС-грамматики Г и для любой цепочки х в основном .словаре Г можно построить НС-грамматику Г' такую, что ЦГ') = (х \ L(T))—{Л}. Аналогично для правого деления.
3.10. Показать, что существуют вычислимые числовые функции f(P> Я) у обладающие следующим свойством: для любой неукорачивающей грамматики, мощность полного словаря и длины левых и правых частей правил которой не превосходят соответственно р и q, можно построить эквивалентную ей неукорачивающую грамматику, длины левых и правых частей правил которой не превосходят соответственно двух и трех, а мощность вспомогательного словаря не превосходит f{p,q). Найти явное выражение одной из таких функций. [Указание. Проанализировать доказательство теоремы 2.1.]
3.11. Показать, что для любой неукорачивающей грамматики можно построить эквивалентную ей почти неукорачивающую грамматику с вспомогательным словарем, состоящим из трех символов.
3.12. Пусть код грамматики определяется, как в доказательстве теоремы 2.4, и пусть J7* — какой-нибудь класс грамматик, основные и вспомогательные словари которых содержатся в некоторых счетных множествах, причем объединение этих множеств не содержит символов, используемых для кодирования. Назовем грамматику Го универсальной для класса Т, если L (Г0) = {х (Г) л: | Г е еГ & iei(r)}, где к (Г)—код Г, Показать, что существует
УПРАЖНЕНИЯ
ИЗ
грамматика Г0, универсальная для класса грамматик без растяжения и такая, что Sro (я) ^ я log2 я.
3.13. Построить ДЭ-машины с ограниченным растяжением, допускающие:
а) каждый из языков упражнения 3.6;
б) множество всех простых чисел в двоичной записи;
в) множество {<*! ... а. | s = 1, 2, ..где а,- — »-й знак дробной части десятичного разложения числа 1^2;
г) то же для числа е.
3.14. Показать, что для всякой ДЭ-машины без растяжения, допускающей язык L, можно построить ДЭ-машину без растяжения, распознающую тот же язык L. [Указание. Если ДЭ-машина без растяжения не допускает цепочку х, то ^-вычисление ведет либо к безрезультатной остановке, либо к уходу головки за пределы «х-зоиы», либо к «зацикливанию» в этой зоне; каждое из этих трех явлений можно обнаружить, не выходя из «х-зоны».]
Замечание. Неизвестно, существуют ли языки, допускаемые Э-машинами без растяжения и не допускаемые ДЭ-машинами без растяжения. Отрицательное решение этой проблемы повлекло бы положительное решение проблемы замкнутости класса НС-языков относительно вычитания и взятия дополнения (ср. замечание 2) к теореме 3.4).
3.15. Дать верхние оценки временных сложностей грамматик, построенных при выполнении упражнения 3.6.
3.16. Оценить сверху возрастание временной сложности при построениях, использованных для доказательства теоремы 3.2. Получить из этих оценок другое доказательство теоремы 3.5.
3.17. Распространить теорему 3.6 на почти неукорачивающие грамматики.
