Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
21В дополнительные сйеДенйя о б-грлмматикАх [ГЛ. 6
Упражнения
6.1. Построить К-грамматики, определяющие:
а) язык {хх | х ?= {cLi.а„}+};
б) язык {anbn \п = 1, 2, .. .)*;
в) множество ппф логики высказываний в бесскобочной записи;
г) язык Дика.
6.2. а) Показать, что для всякой К-грамматики можно построить эквивалентную ей К-грамматику с единственной элементарной категорией [Г. М. Ильин, не опубликовано].
б) Оценить происходящее при этом увеличение сложности грамматики.
6.3. Оценить увеличение мощности словаря категорий при построении по данной К-грамматике эквивалентной ей односторонней К-грамматики сложности, не превосходящей 2 (следствие из теоремы 6.1).
6.4. Показать, что класс языков, определяемых левосторонними (или правосторонними) К-грамматиками сложности, не превосходящей 1, «эффективно совпадает» с-классом А-языков.
6.5. Показать, что класс языков, определяемых произвольными К-грамматиками сложности, не превосходящей 1, «эффективно совпадает» с классом линейных Б-языков.
6.6. Назовем К-грамматику G категориально однозначной, если каждой цепочке языка L(G) она сопоставляет единственную цепочку категорий, и синтаксически однозначной, если всякая цепочка ее категорий, сокращающаяся до ее главной категории, имеет единственное дерево сокращения.
а) Проверить, являются ли грамматики примеров 1, 2, 3 из § 6.1 категориально и синтаксически однозначными.
б) Пусть V — множество ппф логики высказываний в варианте, рассмотренном в примере 3 из § 6.1, но со стертыми скобками. Построить категориально однозначную, но синтаксически неоднозначную К-грамматику, определяющую^//, таким образом, чтобы для каждой цепочки из U имелось взаимно однозначное соответствие между ее деревьями сокращения и расстановками скобок, превращающими ее в ппф.
в) Показать, чтр всякая односторонняя К-грамматика, обладающая тем свойством, что «знаменатели» всех категорий, являющихся частями элементов значений ее приписывающей функции, элементарны, синтаксически однозначна. [Заметим, что грамматика, построенная при доказательстве теоремы 6.1, обладает указанным свойством.]
г) Можно ли распространить результат предыдущего пункта на произвольные односторонние К-грамматики?
д) Построить синтаксически однозначные К-грамматики для языков примеров 1—3 из § 4.4. Показать, что ни один из этих языков не может быть определен категориально однозначной К-грамма-тикой.
6.7. Вывести теорему 6.1 из теоремы 6.2.
6.8. Показать, что линейный язык {атЪп \т,п—\, 2, ...; т ^ п} не допускается никакой одцодорожечной МП-машиной, удовлетворяющей требованию теоремы 6.4.
УПРАЖНЕНИЯ
219
6.9. Показать, что для всякой МП-машины, принадлежащей одному из перечисленных ниже классов, можно построить эквивэлрчт-ную ей МП-машину без растяжения, принадлежащую тому же классу:
а) класс однодорожечных МП-машин;
б) класс чисто стирающих МП-машин;
в) класс МП-машин с ограниченным числом поворотов.
6.16. Назовем дерево подчинения для правильно построенной формулы узкого исчисления предикатов в бесскобочной записи «естественным», если оно построено, как в следующем примере:
ЧхЧу&ГхлЪгБуг.
Построить для множества формул указанного вида Д-грамма-тику, сопоставляющую каждой из них естественное дерево подчинения (и только его).
6.11. Показать, что Д-грамматика, получаемая из К-грамматики О при обратной иерархизации, имеет ограниченную ширину, а при прямой иерархизации, если язык L(G) бесконечен, — неограниченную.
6.12. Показать, что Д-грамматика, получаемая из К-граМматики сложности 1 при прямой иерархизации, имеет высоту 1, а при обратной иерархизации — ширину 1.
6.13. Показать, что длины путей без ветвления *) в деревьях подчинения, сопоставляемых цепочками К-грамматикой С при прямой иерархизации, не превосходят сложности G [Е. И. Подольская, не опубликовано].
6.14. Назовем Д-грамматику G = (Г, f) однозначной, если никакой цепочке она не сопоставляет более одного дерева подчинения. Соответствующую функцию } будем называть «строгой», если все ее значения — одноэлементные множества. Исследовать взаимоотношение между однозначностью С и строгостью f.
6.15. Построить однозначные Д-грамматики (упражнение 6.14) для языков примеров i—3 из § 4.4.
6.16. Показать, что всякая приведенная удлиняющая Б-ОАЕВ-грамматика (§ 5.4) имеет конечную степень.
6.17. Показать, что любая приведенная удлиняющая Б-грамматика, порождающая язык {a”bn\n= 1, 2, ...}, имеет конечную степень.
6.18. Пусть Г — НС-грамматика без правил вида фЛф->фбф, Л, В е W, и фЛ1|; -? фвф, Де W — {/}, а е V. [Такие грамматики порождают не все НС-языки (см. теорему 3.7), но и не только Б-язы-ки (достаточно слегка видоизменить пример 1 из § 3.4).]
а) Обобщить определение Д-грамматики на случай, когда ее первая компонента — НС-грамматика указанного вида.
*) Путь ai, ..., «(+1 называется путем без ветвления, если узлам alt а< подчинены только ag, «f-и соответственно.
220 ДОПОЛНИТЕЛЬНЫЕ СВЕДЕНИЯ О Б-ГРАММАТИКАХ [ГЛ. 6
б) Показать, что при таком обобщении сохраняет силу пункт а) леммы 6.2.
6.19. а) Показать, что решение нормальной системы уравнений единственно, если ни один из членов левых частей не равен одной из переменных gi или произведению нескольких переменных.
