Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
СЛОЖНОСТЬ: ВЫВОДА В 6-ГРАММАТИКАХ
[ГЛ. 1
(разные для разных правил), мы получим слабо бинарную грамматику Г', эквивалентную Г и такую, что
/г(п)<(г-1)-/г(п).
Оценка, доставляемая только что доказанной теоремой, не может быть понижена (во всяком случае, по порядку): существуют Б-языки, не порождаемые никакими Б-грамматиками с активной емкостью, растущей медленнее логарифмической функции (и тем более не являющиеся ОАЕ-языками). Приведем пример.
со
Пример 2. Положим L=[jLk, где Lk — языки
примера 1. Язык L порождается Б-грамматикой со схемой {/—* cAd, I-+cd, A-+aAb, A—+aIIb}. Пусть Г = = .(V, W, /, R)— произвольная порождающая L Б-грамматика, /7 —мощность W и g — максимум длин правых частей правил Г. Можно считать Г, подобно предыдущему, приведенной и не имеющей правил вида А—*В, A, B^ W. Как и в примере 1, мы можем утверждать. (см. замечание на стр. 234), что если цепочка ш е Li, А ^ 1, выбрана так, чтобы для любой ее подцепочки х, являющейся гроздью высоты, большей 0: х = = cantit2bnd {ti и t2 — гроздья), число п было не меньше 2(р-\-\) g2(J>+1), то активная емкость вывода да из / в Г не может быть меньше k. Обозначив через 4 наименьшую длину цепочки из Lk, удовлетворяющей указанному условию, и полагая 4 (р 1) • g2(p+l) -f 2 — h, имеем U^= = h-f 4, 4+i = 2 lk + h, откуда при k^2 получается lk = (2h — l)ik-f- 2h+1 < 2k+i(h + 1), так что k > 1 og2/fe—
— Iog2(/z + 1)—1. Поэтому для бесконечного числа значений п (именно, п = 12, /з, ...) справедливо неравенство /г(«) 5s log2« — log2(ft + 1) — 1, так что во всяком случае отношение /r(«)/log2n не может стремиться к пределу, меньшему единицы. Более того, можно найти такую постоянную с, что /r(n)>log2« — с. Действительно, при любом k — 2, 3, ... имеем, во всяком случае, lk+i<2rlk, где г = log2(/i -f 2); поэтому при lk ^ п < lk+i получаем
h(n)>h{lk)>bg2lk — \og2(h-\- 1) — 1 >
> log2 (/*+,) — г — log2(ft + 1) — 1 >
> log2 п — г — log2 {h -f 1)— 1.
§ 7-21
АКТИВНАЯ ЕМКОСТЬ
237
В заключение параграфа мы укажем характеристику ОАЕ-языков в алгебраических терминах, сходную с полученной в § 5.4 для ОАЕВ-языков. Для этого введем одно новое понятие, представляющее и самостоятельный интерес.
Пусть Т — конечное дерево. Сопоставим каждому его узлу а натуральное число [i(T,a), которое будем называть густотой этого узла, следующим образом.
I. Густота висячего узла равна нулю. II. Пусть для всех узлов рь ..., ps, подчиненных узлу а, числа ц(7\ Pi), ..., |л(Г, ps) определены; тогда: а) если
Pi)= ? ? • = Ps)= 0, то ц(Т,а) — 1; б) если шах ц(Т, Pi) = пг > 0, то: 61) в случае, когда существует только одно i — 1, ..., s, для которого |Л(Т, Pi) = = пг, полагаем ц(Г, а) = т\ 62) в противном случае
Далее, густотой дерева Т (обозначение: ц(Т)) будем называть густоту его корня.
Из определения ясно, что в дереве густоты m все узлы, имеющие ту же густоту т, образуют путь (возможно, нулевой длины), исходящий из корня. Мы будем называть этот путь с т а о ш и м.
Лемма 7.2. Если Т — дерево полного вывода в слабо бинарной Ъ-грамматике, то наименьшая активная емкость вывода, отвечающего этому дереву, равна густоте Т.
Доказательство. Ради удобства индукции бу--дем проводить его для любых (А, л:)-деревьев, где А— вспомогательный символ их — цепочка основных символов. Для дерева высоты 1 утверждение очевидно. Пусть оно доказано для деревьев высоты, меньшей п, и пусть высота Т равна п, а густота равна т. Если среди узлов, подчиненных корню Т, только один помечен вспомогательным символом и Г — полное поддерево Т с корнем в этом узле, то наименьшая активная емкость выводов, отвечающих Г, будет такова же, как для выводов, отвечающих Т', а последняя равна |x(7v) — tn. Пусть имеются два узла, подчиненных корню Т и помеченных вспомогательными символами, и пусть Т', Т" — полные поддеревья Т с корнями в этих узлах. Возможны два случая: а) (л(Г') = \х{Т") — m— 1; б) густота одного из деревьев Т', Т" — пусть Т' — равна пг, а
238
СЛОЖНОСТЬ ВЫВОДА в б-грамматиках
[ГЛ. 1
густота второго меньше т. В обоих случаях наименьшая активная емкость вывода, отвечающего Т, получится, если сначала выполнить вывод наименьшей активной емкости, отвечающий Т", а потом — отвечающий Т' (впрочем, в случае а) можно и в обратном порядке); и в обоих случаях в силу индуктивного предположения получится вывод активной емкости т.
Перейдем теперь к алгебраической характеристике ОАЕ-языков. Эту характеристику можно сформулировать очень просто: класс ОАЕ-языков совпадает с замыканием класса линейных Б-языков относительно подстановки. Мы, однако, постараемся уточнить формулировку так, чтобы она стала эффективной. Для этого введем следующее определение.
Будем называть подстановочным выражением от (переменных) Si, ..., |п всякое выражение, составленное из абстрактных символов Si, ..., \п с помощью знаков подстановки (в обозначениях подстановок должны участвовать также некоторые элементарные символы, причем каждой переменной, выступающей в роли языка, в которой производится подстановка, сопоставляется определенный набор элементарных символов; ср. определение центрально-подстановочного выражения, являющееся частным случаем настоящего определения, на стр. 177). Например, если Si, •••> Ss — переменные и а, Ь, с, d, е — элементарные символы, то s(tu a, b,?\S2, S(Si; а, Ь, cjSs, |4, Ss), $(Ы b, d, е\ S(|7; а|Ss), \d], {е}))—подстановочное выражение; переменным Si, S4 и S7 здесь сопоставлены наборы {а, Ь, с}, {b, d, е} и {а} соответственно. Обычным способом определим также представление языка с помощью подстановочного выражения.
