Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
[Указание. Доказать нераспознаваемость в классе линейных ОБ-грамматик с основным словарем [а, Ь, с, d, е} свойства языка иметь непустое пересечение с L0{d, е}*, где L0 = {хсх\х е {а, 6}*}. При этом можно рассуждать по аналогии с доказательством теоремы 8.5.]
8.15. Используя упражнение 8.14, доказать нераспознаваемость однозначности грамматики в классе Бу, где Ц(У) ^2.
8.16. Указать алгоритмы, распознающие для любых ОА-грамма-тик (а тем самым и для любых ОБ-грамматик с одноэлементным основным словарем — см. замечание к теореме 4.6) свойства и отношения, перечисленные в следствиях из теоремы 8.4.
8.17. Показать, что если L — рекурсивный язык, то для любой цепочки х дополнения к множествам ФХ(Ц и ^(L) (см. стр. 318) рекурсивно перечислимы.
8.18. Пусть R — рекурсивное множество точек целочисленной плоскости (т,п) (т,п = 0, 1, ...’), проекция которого на ось т не рекурсивна. Положим
h = {bban+1 \п = О, I, ...} U {am+Iban+11 (т, п) ф /?};
1-2 = {{bam+lb)p (Ь2ап+1Ь2)Ч\ (т, п) <? R- р, q = 1, 2, ...} U
U {{bam+lbfP {b2an+lb2)41 (m, п) е R\ р, q = 1, 2,
Показать, что:
а) множества ®ftj,(Lt) и 4^** (Z-О не рекурслвны;
б) для любой цепочки х е {а, 6}* множества Фx(L2) и 4fx(Lj) рекурсивны, однако Ф (L2) и V (Li) не рекурсивны.
[Гладкий 1963 (б)].
8.19. Показать, что для любого рекурсивного языка L в одноэлементном словаре Ф(Ь) и 'F(L) рекурсивны [Гладкий 1963 (б)].
8.20. Построить линейный язык в двухэлементном словаре с неразрешимой проблемой распознавания конфигураций.
8.21. Указать примеры линейных языков, для которых не существует алгоритмов, позволяющих по заданной цепочке х распознать:
а) является ли х конфигурацией заданного ранга г (для каждого г — свой язык);
б) является ли х конфигурацией.
[Лучкин 1966].
[Указание. Использовать конструкцию упражнения ПП. 7.]
8.22. Показать, что не существует алгоритма, позволяющего для любой Б-грамматики Г найти наименьшее число вспомогательных символов Б-грамматики, эквивалентной Г. [Указание. Использовать упражнение 4.21.]
I
ПРИЛОЖЕНИЕ I
СИСТЕМЫ СОСТАВЛЯЮЩИХ И ДЕРЕВЬЯ СИНТАКСИЧЕСКОГО ПОДЧИНЕНИЯ
В современной лингвистике используются различные способы описания синтаксической структуры предложения, из которых наиболее употребительны два — описание с помощью систем\составляющих и описание с по- ; мощью деревьев синтаксического подчинения. Мы дадим 4 здесь краткое изложение этих способов, а также-правил перехода от одного способа к другому.
§ П1.1. Системы составляющих
Пусть х — произвольная непустая цепочка в словаре V. Множество С отрезков цепочки х называется системой составляющих этой цепочки, если оно удовлетворяет следующим двум условиям:
I. С содержит отрезок, состоящий из всех точек цепочки х, и все одноточечные отрезки я.
II. Любые два отрезка из С либо не пересекаются, либо один из них содержится в другом.
Элементы С мы будем называть составляющими. Одноточечные отрезки будут называться точечными составляющими, отрезок, состоящий из всех точек цепочки, — полной составляющей; полную и точечные составляющие мы будем иногда называть тривиальными.
Для наглядного изображения системы составляющих можно пользоваться следующим простым способом: заключать каждую нетривиальную составляющую в скобки, причем левую и правую скобки, отвечающие одной составляющей, помечать одной и той же меткой так, чтобы разные пары скобок были помечены разными метками;
§ П.IЛ]
СИСТЕМЫ СОСТАВЛЯЮЩИХ
283
в качестве меток можно использовать хотя бы натуральные числа. Можно, впрочем, обойтись и без меток, так как в силу пункта JI определения системы составляющих для каждой левой скобки можно однозначно указать соответствующую ей правую и обратно (упражнение П1.1). Мы будем пользоваться скобочным изображением как с метками, так и без меток — где как удобнее.
Пример. Две разные системы составляющих (из многих возможных — см. упражнение П1.2) одной и той же цепочки babcadebaccdabab можно изобразить так-
(1) (((ba)b)ca (deb)) ((асс) (d (ab)) (ab));
123 3 2 4 4156 6 7 8 . 87.9 . 9 5-
(2) b(a(b(c(ad(e(ba(cc)d)a)))bab)).
1234 56 776543 21
Если цепочка интерпретируется как предложение' естественного языка, то система составляющих может быть использована в качестве способа выражения информации о его синтаксической структуре (или, , как обычно говорят, способа изображения синтаксической структуры предложения). Именно, такая информация может представлять собой список словосочета? н и й, т. е. тех «кусков» предложения, которые в каком? то интуитивном смысле являются «синтаксически связными». Эмпирические соображения позволяют сделать допущение, что словосочетания, во-первых, образуют .отрезки и, во-вторых, не имеют «частичных пересечений», т. е. удовлетворяют пункту II определения системы составляющих. Таким образом, нетривиальные составляющие— это (при подходящем выборе системы составляющих!) как раз словосочетания. (Тривиальные добавляются для придания системе формальной законченности.) - . - - .
Пример. Предложение
(3) Онегин, добрый мой приятель,
родился на брегах Невы . . „;,г.
