Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
левых частей правил fug грамматики Гг (см. доказательство теоремы о сжатии) не превосходят двух, а правых — трех.
К Гг применим теперь конструкцию леммы о сцеплении со следующими видоизменениями: правила 3-го и
92
ГРАММАТИКИ СОСТАВЛЯЮЩИХ
[ГЛ. 3
4-го рода будут определяться иначе, а именно: правила 3-го рода будут иметь вид а(со) —*? <о, где со — произвольная непустая цепочка длины, не большей 21, в основном словаре Гг (/ имеет тот же смысл, что и в доказательстве теоремы о сжатии), а правила 4-го рода — вид (а(со))°а—*соа, где со — произвольная цепочка длины, не большей 21, в основном словаре Гг и а — произвольный основной символ Гг,' кроме того, правилам h грамматики Г2 не будут сопоставляться правила 1-го рода. Полученную так грамматику мы обозначим Гз.
Если t — длина вывода в Г2, т — длина соответствующего вывода в Гз и ти т?., тг, «4 имеют такой же смысл, как в доказательстве леммы о сцеплении, то, рассуждая, каквэтом доказательстве, мы получаем т%^ (3-j-1)= = 4rti\ ^ At (поскольку длины правых частей тех правил Гг, которым сопоставляются правила 1-го рода, не превосходят трех, а разности длин левых и правых частей этих правил — единицы; кроме того, t = тхтгтС). Отсюда т^.Ы. Таким образом, Trs(ti) ^.5ТгЛп)- При этом каждое правило 1-го рода грамматики Г3 имеет один из следующих шести видов:
(О Pi^Yi;
(И) p,->yiy!>;
(Ш)
(iv) P?P2^YiY2,-
(v) PjPg-^YiYsYii;
(vi) PjPg-^.YiYgYs-
Построим теперь по грамматике Гз НС-грамматику Г4 следующим образом: а) Каждое правило 1-го рода вида (iii) — (vi) и каждое правило 2-го рода заменим некоторой системой новых правил, которую мы выпишем только для случая правил 1-го рода вида (v) и (vi) (для остальных случаев система строится совершенно аналогично). Для правила вида (v): PiP? —> FpO; -*
FY^y®-*- YiY^Y”- Для правила вида (vi): Р?Р2 —^Р?-^;
-> GF; GF->Gy°2yf, GY^^Y,Y^. Здесь F, G — новые символы, разные для разных правил, которые мы присоединяем к вспомогательному словарю грамматики.
§ 3 11 ОПЕНКА ВРЕМЕННОЙ СЛОЖНОСТИ НС-ЯЗЫКОВ 93
б) Правила 1-го рода вида (i) и (ii), а также правила З-ю и 4-го рода переносятся в схему Г4 без изменения. Грамматика Г4 эквивалентна Гз, поскольку, с одной стороны, применение каждого правила Гз можно заменить применением соответствующей системы правил Г4, с другой — в каждом полном выводе в Г4 правила одной системы могут применяться только подряд (ввиду того, что цепочка, входящая в полный вывод в Гз, не может содержать более одного вхождения символа вида \), и поэтому вместо каждой такой системы можно применить соответствующее ей правило грамматики Г3. Очевидно также, что Гг,(п) ^ 4Гг3(«).
Итак, мы имеем Гг, (я) ^ 20 [Гр, (л) + шах (c2n, 1)].
Если положить с2 — - j ip t , гда dx — максимум разностей длин правых и левых частей Г] (d{ эффективно определяемо по Г и Cj), то в силу последнего из неравенств (2) § 2.1 будет C2tt<Tr,(n), так что Гг4(га)^40Гг,(л)^ <|40тах(1, с,Гг(л)). Положив с{ — с/40, получим Trt(n)^ ^ max (40, сГг(п)). Остается добавить к схеме Г4 всевозможные правила вида 1-*х, где / — начальный символ Г4, ^е1(Г4) и | 40d4 + 1 (d4 — максимум разностей
длин правых и левых частей правил Г4); поскольку среди таких цепочек содержатся все выводимые в Г4 не более чем за 40 шагов, имеем для полученной таким образом НС-грамматики Г': 7V(«)<[max(l, сТт(п)).
Замечание. Из теоремы 3.6 вытекает, что в теореме 3.5 квантор существования по г можно заменить квантором общности.
В заключение заметим, что операторы левой и правой глубины, разброса и активной емкости (точнее, соответствующие относительные операторы) являются для класса неукорачивающих грамматик сигнализирующими и соответствующие сигнализирующие функции для любой неукорачивающей грамматики рекурсивны. (Это частный случай утверждения упражнения 2.10,6).)
§ 3.4. Оценка временной сложности некоторых НС-языков
Как отмечалось в предыдущем параграфе, временная сложность любой НС-грамматики заключена между линейной и показательной функциями. Естественно
94
ГРАММАТИКИ СОСТАВЛЯЮЩИХ
[ГЛ. 3
возникает вопрос: можно ли усилить эту тривиальную оценку, т. е. найти такую функцию f{n), растущую медленнее показательной, чтобы имело место равенство 3?Tf (НС) = 3 (НС) *)? К сожалению, ответить на этот вопрос мы не можем. Мало того, неизвестно даже, верно ли соотношение 9?ni (НС) = 3 (НС). Единственный результат, имеющийся пока что в указанном направлении, состоит в том, что ни для какой функции h(n), растущей медленнее, чем п2, равенство 31 (НС) = 3 (НС) не имеет места. Доказательство этого и будет основной целью настоящего параграфа.
Начнем с введения некоторых вспомогательных понятий. Пусть Г — НС-грамматика, D = (®0, ..., соп)—вывод в Г такой, что | coo | = 1, Т'— какое-либо растянутое дерево вывода D и М'— множество узлов Т'. Распространим отношение «быть предком» («быть потомком»), определенное на М', на множество подмножеств М', являющихся интервалами цепочек too, • •., соп. Именно, если 0^г</^л и Q — интервал цепочки ©j, мы будем называть предком Q в цепочке «г наибольший непустой интервал этой цепочки, для которого все потомки его точек, являющиеся точками со;-, принадлежат Q; если же такого интервала нет, то предком Q в цепочке сог мы будем считать любой пустой интервал tDi, включая несобственные интервалы (—, у) и (б, —), где у и 6 — соответственно первая и последняя точки ©г-. Если Q имеет непустого предка в цепочке со,-, то других предков Q в этой цепочке не существует. Интервал цепочки «j, для которого Р является предком в шг-, будет называться потомком Р в цепочке coj.
