Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
Пу?ть а и р — два узла некоторого дерева Т полного вывода в Г, помеченные одним и тем же символом и такие, что р зависит от а. Если v и у— составляющие, «происходящие» от а и р соответственно, то » = xyz, A h- xAz, откуда А (— xnAzn для любого п= 1, 2, причем хотя бы одна из цепочек х и г не пуста. Поэтому ввиду свойства VI х = a1, z = bl, у = = alviv2b\ где v\ и v2— гроздья.
Выберем совершенную гроздь w высоты ft так, чтобы для любой ее подцепочки х, являющейся гроздью высоты, большей 0 и представимой в виде х —
— cantit2bnd (ti и t2 — гроздья), число п было не меньше 2(р + 1)-g2(-P+1\ где р — мощность W и g — максимум длин правых частей правил Г. Фиксируем некоторую систему составляющих С, сопоставляемую цепочке w некоторым выводом в Г, — соответствующее дерево вывода обозначим Т — и рассмотрим одну из подцепочек-гроздьев цепочки w: х = cut\i2vd, где и = ап, v —
— bn, 11 и t2 — гроздья. По лемме III.1 в системе С найдется р +1 составляющих, образующих вложенную последовательность: y\Z^y2=> ... гэУц+\ — и таких, что либо левые, либо правые концы их попарно различны и содержатся в отрезке и. Узлы аь а2, • • •, ap+i дерева Т, от которых «происходят» у\, г/2, • • •. Ур+1 соответственно, лежат на одном пути, и по крайней мере два из них пусть уf и ун, f <~ h, — помечены одним и тем же символом. По предыдущему отсюда следует, что у; = а1 уф1, yh = a'ViVzbi, где i>i, v2 — гроздья. Теперь во всяком
234 СЛОЖНОСТЬ ВЫВОДА В Б-ГРАММАТИКАХ [ГЛ. 7
случае ясно, что отрезок и содержит левый конец уь, так что yh = amt', причем либо t' — начало t\t2, либо t\t2— начало t'. Поскольку и t\t2, и ViV2 начинаются символом с, имеем т = i. Следовательно, либо t\ — начало v\, либо Vi — начало t\\ но никакая гроздь не может быть собственным началом другой, так что t\ — v\, откуда точно так же t2 — v2. Итак, ун = аЧ^ЬК Таким образом, каждой грозди х, являющейся подцепочкой w, отвечает составляющая у(х) = ун, содержащаяся в х и содержащая всякую гроздь, являющуюся собственной подцепочкой х. Пусть теперь С' — множество всех составляющих из С, сопоставленных таким способом всевозможным подцепочкам w, являющимся .гроздьями (включая самое w). Ясно, что С' есть ^-система. Доказательство закончено.
Замечание. Все рассуждения, относящиеся к грамматике Г, очевидно, сохраняют силу для любой Б-грамматики, которая а) порождает все гроздья высоты k и б) не порождает ни одной цепочки, не являющейся гроздью. Мы воспользуемся этим ниже при разборе примера 2.
Назовем Б-грамматику, активная емкость которой мажорируется константой, Б-грамматик.ой ограниченной активной емкости, сокращенно Б-ОАЕ-грамматикой, а язык, порождаемый такой грамматикой, — ОАЕ-языком. Всякая Б-ОАЕВ-грамматика (§ 5.4) является Б-ОАЕ-грамматикой (причем, если /0(Г) = й, то Ir(n)^k). Грамматики Г* примера 1 являются не только ОАЕ-, но и ОАЕВ-грамматиками; однако легко видоизменить этот пример так, чтобы ни один из получаемых языков не был ОАЕВ-языком. Положим, например, L'k=LkLn, где LQ = {anbn\n = = 1,2Можно показать —это предоставляется читателю, — что ни один из L'k не является ОАЕВ-языком (ср. упражнение 5.27). В то же время для каждого L'k легко построить порождающую его Б-грамматику Г* такую, что /г/ (п) = k + 1; кроме того, нетрудно убедиться, опираясь на соответствующий результат, уже цмеющийся для языков Lft, что Ь'%ф. i??(B).
Таким образом, уже класс ??2(Б) содержит языки, не являющиеся ОАЕВ-языками. (Что касается класса
АКТИВНАЯ ЕМКОСТЬ
235
S?\ (Б), то он, как уже отмечалось, совпадает с классом линейных языков.)
В общем случае для активной емкости можно получить более низкую верхнюю оценку, чем для глубины и разброса: имеет место
Теорема 7.4. Для любой Ъ-грамматики Г справедливо неравенство /г(n)^.(r — l)-(log2«-f 1), где г есть максимум длин проекций правых частей правил Г на вспомогательный словарь, если этот максимум не меньше двух, и г = 2 в противном случае.
Доказательство. Ради удобства индукции установим несколько более общий факт: если Г = (У, W, l,R) — Б-грамматика, А е W, хеУ+ и А Н х, то найдется вывод х из А в Г, активная емкость которого не превосходит (г—1) (log2|x|-f 1). Ограничимся сначала случаем, когда г ^ 2, т. е. правая часть каждого правила Г содержит не более двух вхождений вспомогательных символов. (Грамматику, удовлетворяющую этому условию, мы будем называть слабо бинарной.) При | х | = 1 утверждение очевидно. Пусть оно доказано для цепочек длины, меньшей п, и пусть \x\=nnD — произвольный вывод х из А. Пусть далее ю — первая цепочка вывода D, содержащая два вхождения вспомогательных символов (если такой цепочки нет, то все доказано): а = = tBuCv, В, Cef, t, и, tie V*. Тогда х = tyuzv, где В 1— у, С Ь- z. При этом длина хотя бы одной из це-г г
почек у, z — пусть у — не превосходит л/2. По индуктивному предположению можно найти вывод D' цепочки у из В и вывод D" цепочки z из С, активные емкости которых не превосходят соответственно Iog2|#|+l^ =s;log2n и log2|z| -f 1 sg: log2 n -f 1. Производя сначала все шаги вывода D до получения цепочки а, затем все шаги D' и, наконец, все шаги D", будем иметь вывод х из А активной емкости, не превосходящей log2/г 4-1-Доказательство для общего случая получается теперь из следующего почти очевидного замечания: заменив в произвольной Б-грамматике Г = (V, W, /, R) каждое правило А z0BiZiB2Z2... zs-iBszs, где Ви ..., Bs е ef; 20, ..., 2,eV*, s > 2, системой правил А —*? —1? ZoBiZiCi, С{ —? B2Z2C2, ..., Cs-3~Ss_22s-2C,_2, Cs-2 —? Bs-iZs-iBa*, где С ..........Cs-2 — новые символы
