Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
части индекс ш, а в правой части: а) при i < t приписать Рис- 14.
тому вхождению вспомогательного символа, которое отвечает узлу a,-+i, индекс т, а вхождению, отвечающему узлу Pj (если оно есть), индекс ш3; б) при i — t приписать каждому из двух вхождений вспомогательных символов индекс т — 1 (заметим, что mu~i — ти = т—1). Очевидно, все r'i, i = = 1, ..., t, — правила грамматики ГАт.
Среди отвечающих дереву Т выводов имеется такой, в котором на первых t + 1 шагах применяются правила ''о, г\, .. . , rt (в этом порядке) и притом как раз в точках, соответствующих узлам ао, . - -, at. После выполнения этих шагов получается цепочка со, содержащая и + 1 вхождений вспомогательных символов, а именно символов, являющихся метками при Ро, .. ., Заменяя в со каждое вхождение вспомогательного символа 60), отвечающее узлу р;-, вхождением символа Вт , получим цепочку со', которая, очевидно, получается из Ат последовательным применением правил г'о, г\, ..., r't и, следовательно, принадлежит L(Ya,т)- Но цепочка х
символов (один из них является меткой при аг+ь а другой, если он имеется, — меткой при некотором Pj, / г), а если
i — t — точно два вхождения (являющиеся Метками при Pu-i и рм). Обозначим через ri правило, которое получится из г и если приписать левой
Ри §4-1
*) Каждому из узлов а0........ ai_i может быть подчинен самое
большее один узел, помеченный вспомогательным симзолом и hi; лежащий на старшем пути; для a( таких узлов ровно два.
242
СЛОЖНОСТЬ ВЫВОДА в б-грамматиках
[ГЛ. 7
получается из to, а значит и из со', заменой каждого вхождения вспомогательного символа, отвечающего узлу Pj, на цепочку Zj = ц(Т}) \ а поскольку Т, есть (В{1), Zj)-дерево густоты m,j < m, имеем zt е m.. Однако язык,
получающийся из Z,(rAfn) подстановкой языков Lb, вместо символов Bm', т' < т, — это и есть Z-л, m-
Замечание. В настоящем параграфе, как и во всей главе, мы ограничились случаем Б- (а не ОБ-) грамматик, чтобы избежать дополнительного усложнения рассуждений, дающего не слишком большой выигрыш в общности. Однако соответствующие обобщения могут быть сделаны без труда.
§ 7.3. Степень гнездования и степень самовставления
В § 3.1 мы ввели НС-сигнализирующие— специфические характеристики сложности вывода в НС-граммати-ках, при определении которых существенным образом используется представление вывода в виде дерева. Там же были определены три конкретных типа НС-сигнали-зирующих: Yr, Y? и Фг. Для Б-грамматик, как мы видел^ в § 7.1, функции Уг и Y? совпадают, с точностью до аддитивной постоянной, с левой и правой глубиной соответственно. Нам остается изучить (для случая Б-грамматик) поведение функции Фг (п), которую мы будем называть степенью гнездования грамматики Г. Параллельно с ней мы будем рассматривать другую функцию — степень самовставления (обозначение: Хг (п)), — определяемую следующим образом: (i) назовем гнездо, содержащееся в системе составляющих, отвечающей дереву вывода в Б-граммати-ке, однородным, если все входящие в него составляющие «происходят» от узлов с одинаковыми метками (причем, если какая-нибудь составляющая «происходит» от нескольких узлов, то достаточно, чтобы один из них имел нужную метку); (ii) степенью самовставления дерева полного вывода Т в Б-грамматике Г (обозначение: Х(Г, Т)) назовем наибольшую глубину однородного гнезда, содержащегося в отвечающей Т системе составляющих; (iii) для произвольной цепочки Jf^L(T) по-
§ 7.3) СТЕПЕНЬ ГНЕЗДОВАНИЯ И САМОВСТАВЛЕНИЯ 243
ложим X (Г, х) = min %(Г, Т) где минимум берется по всем деревьям вывода цепочки х из начального символа в Г; (iv) наконец, Хг (n) = max X (Г, х).
x<=L (Г); \х\ < п
Из определений ясно, что Хг (п) ^ Фг (п). В то же время, если р — мощность вспомогательного словаря Г, то во всяком гнезде глубины, не меньшей рп, содержащемся в отвечающей дереву вывода в Г системе составляющих, будет содержаться, в свою очередь, однородное гнездо глубины, не меньшей п\ поэтому Фг (п) ^ < рХг (п).
Как было уже замечено (стр. 84),
®r(n)<min(Y?(n), У?(/г)).
Поэтому из теоремы 7.1 и ее аналога для правой глубины' следует, что для Б-грамматик Фг (я) ^
<min(^r(n), Vv («)) + е — 1, где е — максимум длин цепочек х в основном словаре Г, для которых в Г имеются правила вида А -> хВ или А -> Qx, причем 0=^=Л *). В частности, для стандартной бинарной Б-грамматики
Фг(«)<гшп(^(/г), а?г{п)) — 1.
В силу определения гнезда имеем (для любой НС’
грамматики) Фг(«)^у(«—1); это неравенство может
переходить в равенство уже для линейных грамматик (например: {/—? а/а, / —*- а} ). Для любой Б-грамматики Г и любого действительного числа с, 0 < с ^ 1, можно построить Б-грамматику Г', эквивалентную Г и такую, что (для достаточно больших п) Фг' («) ^ сп (в силу аналогичного факта для левой глубины, стр. 225). Вместе с тем даже для линейного языка может оказаться, что степень гнездования (а значит, и степень самовставления) каждой порождающей его Б-грамматики мажорирует некоторую линейную функцию. В частности, это верно для языка примера 1 из § 7.1. Действительно, мы можем, как и в этом примере, ограничиться приведенными грамматиками без правил вида А—*В, A, Be W (ни устранение таких правил, ни переход к приведенной грамматике не меняют степеней гнездования деревьев полных выводов); но при разборе примера мы видели,
