Гладкий - Формальные грамматики и языки - 1973 (947381), страница 22
Текст из файла (страница 22)
Заметим теперь, что для данной грамматики Г существует такая эффективно по ней вычисляемая постоянная с, что для каждой цепочки х ен 1.(Г) среди цепочек, принадлежащих Гз-образу (-з, найдется хотя бы одна цепочка 7гхг, для которой (г1 ( с)х). (Это следует из того, что среди нормальных выводов цепочки х найдется хотя бы один бесповторный, длина которого мажорируется показательной функцией от !х(.) Фиксируем натуральное число 1 ) 2(2с + 1). Сопоставим каждой цепочке Ч длины, не большей 21, состоящей из символов, входящих в словари всех рассмотренных нами грамматик, новый символ а(ч(). Определим понятие образа цепочки аналогично тому, как это было сделано а доказательстве теоремы 2.1, используя число 1 вместо фигурировавшего там 1.
С помощью того же метода «блочного кодирования», который был применен в указанном доказательстве, легко преобразовать грамматику Гз в грамматику Гз, обладающую свойством 1) г(!амматики Г, и сверх того следующим свойством: 2) Гз-образ языка Я Н~Гг" И О" (й, т, и=О, 1, ...) состоит из всевозможных цепочек вида пи!хасс(г) !х(х) а(г), где х ~Т.(Г),2 †двоичн запись длины некоторого нормального вывода х, й — некоторый специальный символ, й = О, 1, ... и !х(го) означает образ цепочки оь В силу выбора числа 1 для каждой цепочки х ~ Т. (Г) найдется такая цепочка т = ~ Расс(г)а(х)а(г), принадлежащая Гз-образу языка Я Ньб«О"'6"!й, т, и = О, 1... ), что (Х! = 1х).
Теперь для завершения конструкции достаточно построить грамматику Г,, удовлетворяющую тому.же условию 1) и такую, что а) для всякой цепочки х ев Г«и всякой цепочки 1( = ~ )!асс(г)а(х)а(2), где ген (О, !)* и )Х) = (х(, из 1( в Г, выводима х; б) цепочка хек выводима в Гз из цепочки вида $- .Й'а(г)а(и)сс(г), где и я (г", ген (О, 1)', лишь тогда, когда это имеет место согласно пункту а). Принцип работы Гз может быть охарактеризован так. Пользуясь тем же представлением грамматики как машины, которое было использовано при построении Г,, будем считать ленту «четырехэтажной».
Начальная информация записана в первом этаже. Работа начинается с того, что кусок первого эгажа, являющийся образом х, переписывается в правый конец второго этажа. Затем в третьем этаже записывается произвольная цепочка у ~ (у*; после этого в правом конце четвертого этажа записывается (произвольный) образ у; наконец, содержимое второго и четвертого этажей сравнивается, и в случае их совпадения уничтожаются все этажи, кроме третьего. Доказательство теоремы закончено. Упражяепвя 3.1. Построить дерево вывода в растянутое дерево вывода цепочка Ьа"Ь в грамматике примера 1 кз $3.4.
3.2. Показать, что одному размеченному выводу в НС-грамма. тике Г может отвечать более одного растянутого дерева вывода тогда и только тогда, когда схема Г содержит правило вида !РА(чп) ЗВ!р-+!ГА(зп)"'АЗВ!р, где А,  — вспомогательные символы, Ч ча А, л = О, 1, ..., Ь 1, 2, ..., причем левая часть этого правила входит хотя бы в одну цепочку, выводимую яз какого-лабо вспомогательного символа. З.З. Показать, что для всякого сжатого дерева вывода Т а НС- грамматике Г яайдется такой бесповторный размеченный вывод В а Г, что одко яз сжатых деревьев, отвечающих В, совпадает с Т.
3.4. Подсчятать число деревьев вывода я сжатых деревьев вывода цепочки а'"Ьзз в грамматике со схемой (1-»А, ! -»В, А -ь аАЬ, А -ь аЬ, В -+ а'ВЬ, В » а ВЬ', В -+ а'Ь, В -+ аЬ'1. З.б. а) Показать, что для каждой НС-грамматякп Г имеет место неРавенство Уг ~""'Уг (а) + !(, где с(-макскмУИ длвп цепочек 113 УПРАЖНЕНИЯ ГРАММАТИКИ СОСТАВЛЯЮЩИХ (гл.
а 112 х в основном словаре Г, для которых существуют правила Г; имеющие внд «РАф -» фх9ф. Аналогично дла Уг и Уг. б) Построить НС-грамматику Г такую, что у~г (и) =. 1, ~г~ (п)=и. 3.6. Построить неукорачиваюшие или почти неукорачивающие грамматики, порождающие следующие языки: а) (хх [ х ом (а, ..., аз)+з); б) (а~!аз ... а~а~а=1, 2, ...) (й — фиксированное натуральное число); в) (а"Ьма"Вм [ т, и 1, 2, ...); г) (я[хоп(а, ..., аа, Ь, ..., Ь,)+; [х[ [х[ь (г 1,...«3)~; д) множество всех простых чисел в простейшей записи; е) (хоу«г[ху=г), где х, у, г — двоичные записи натураль. ных чисел х, у, г соответственно. 37.
Коммутативным замыканием языка Ещ ш(ао, ..., аэ7' называется изык (х[х ш(ан.... аз)" йэу(уом оп Ей[я[„=[у[, ! 1,..., А). Показать, что: а) коммутативное замыкание НС-языка есть НС-язык (причем по любой НС-грамматике Г можао построить НС-грамматику, порождающую коммутативное замыкание Е(Г)); б) обратное неверно (более того, даже неперечислнмый язык может иметь в качестве коммутативного замыкания язык (аь а»)"). 3.8. Показать, что для любой НС-грамматики можно построить эквивалентную ей грамматику без растяжения, не являющуюся по. чти неукорачнваюшей, 3.9.
Показать, что для любой НС-грамматики Г н для любой цепочки х в основном .словаре Г можно построить НС-грамматику Г' такую, что Е(Г') (х'з Е(Г)) — (Л), Аналогично для правого де. пения. 3.10. Показать, что существуют вычислимые числовые функции [(р, д), обладающие следующим свойством; для любой неукорачивающей грамматики, мощность полного словаря и длины левых и правых частей правил которой не превосходят соответственно р и 4, можно построить эквивалентную ей неукорачивающую грамматику, длины левых и правых частей правил которой не превосходят соответственно двух н трех, а мощность вспомогательного словаря не превосходит [(р,у). Найти явное выражение одной из таких функций.
[Указание. Проанализировать доказательство теоремы 2.Ц 3.11. Показать, что для любой неукорачнвающей грамматики можно построить эквивалентную ей почти неукорачивающую грамматику с вспомогательным словарем, состоящим из трех символов, 3.!2. Пусть код грамматики определяется, как в доказательстве теоремы 2.4, и пусть а — какой-нибудь класс грамматик, основные и вспомогательные словари которых содержатся в некоторых счет. ных множествах, причем объединение этих множеств не содержит символов, используемых для кодирования.
Назовем граммагикч Го универсальной для класса 6«, если Е(Го) =(и(Г) х[Г ом «ма Уох«ЯЕ(Г)), где м(Г) — код Г, Показать, что существует грамматика Го, универсальная для класса грамматик без растяжения и такая, что 8мг (и) ~(п!о3 и. 3.13. Построить ДЭ-машины с ограниченным растяжением, допускающие: а) каждый нз языков упражнения 3.6; б) множество всех простых чисел в двоичной записи; в) множество (а, ... со, [з 1, 2, ...), где ао — 1-й знак дроб. ной части десятичного разложения числа В' 2; г) то же для числа е.
3.14. Показать, что для всякой ДЭ-машины без растяжения, допускающей язык Е, можно построить ДЭ-машнну без растяжения, распознающую тот же язык Е, [Указание. Если ДЭ-машина без растяжения не допускает цепочку х, то х-вычисление ведет либо к беар езультатной остановке, либо к уходу головки за пределы «х-зоны», либо к «зацнклнванию» в этой зоне; каждое из этих трех явлений можно обнаружить, пе выходя из «х-зоны».) 3 а м е ч а н и е.
Неизвестно, существуют лн языки, допускаемые Э-машинамн без растяжения н не допускаемые ДЭ-машинамн без растяжения. Отрицательное решение этой проблемы повлекло бы положительное решение проблемы замкнутости класса НС-языков от. носнтельно вычитания н взятия дополнения (ср, замечание 2) к теореме 3.4). 3.16. Дать верхние оценки временийх сложностей грамматик,по. строенных при выполнении упражнения 3.6. ЗА6. Оценить сверху возрастание временибй сложности прн построениях, использованных лля доказательства теоремы 3.2.
Получить из этих оценок другое доказательство теоремы 3.6. 3.!7. Распространить теорему 3.6 на почти неукорачнваюшие грамматики. 3.18. Назовем грамматику Г= (У, йт, Е )с) обобщенной НС грамматикой (ОНС гр а ми а тиной), если каждое ее правило имеет вид й,А~ — «-Щ, где А ом йг и в«, $«, 0 ен (У () (У)". Показать, что для произвольной грамматики можно построить эквивалентную ей обобщенную НС-грамматику и притом без увелнчения временной сложности. [Указание. Рассуждать по аналогии с доказательством теоремы 3.6.) 3.19. Для каждой из следующих функций фо построить неукора. чиваюшую грамматику, порождающую язык Еэ и такую, что ее вре! менная сложность мажорируется квадратичной функцией: ф«(х) = ВхВ; ф,(х) = Ьхб; «р,(х) = ЬШЬ, 3.20.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
