Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
Теорема 7.5. а) Для любого подстановочного выражения 91 (Si, ..., in) и любых п линейных Ъ-грамма-тик Гь ..., Гп можно построить Ъ-ОАЕ-грамматику,
порождающую язык 9l(L(Ti)......... L(r„)). б) Для
любой Ъ-ОАЕ-грамматики Г можно, если известно число, мажорирующее /г (п), построить подстановочное выражение Щ(Si, ..., Sn) и линейные Ъ-грамматики Гь ... ..., Гп такие, что L (Г) =91 (L (Г4), ..., L (Гп)).
Доказательство, а) Достаточно показать, что по любым Б-ОАЕ-грамматикам Г, Гь ..., Г8 можно
АКТИВНАЯ ЕМКОСТЬ
239
построить Б-ОАЕ-грамматику, порождающую язык S(L(T)\ аи ..., а^МГ,), L{Г,)). Но если Г =
= <1/, W, I,R), Гг = <1/Ь Wi,Ii, Rt) (/ = \,...,s), V = = {a|, aj, словари V{JW, Wh ..., Ws попарно не пересекаются и при этом h(n)^k, h{n)^ki
(г = 1, . • •, s),jo, положив Г' — (У, U • U Vs, W\]Wl\j...
... (J И7*, U R U Ri U • • • U Rs)< гДе Я получается из R заменой во всех правилах всех вхождений ах, ..., as на Is соответственно, будем иметь, очевидно,
/г'(я)^ k + max (fej, .ks)— 1. В то же время ясно, что Г' порождает нужный язык.
б) Пусть Г = (V, W, I, R) — Б-грамматика такая, что /г (п) ^ М, Замечание, сделанное в конце доказательства теоремы 7.4, позволяет при соответствующем увеличении М считать Г слабо бинарной, так что М будет также верхней границей густот деревьев полных выводов в Г (лемма 7.2). Можно также считать, что в Г нет правил вида А —>В, А, В е W.
Сопоставим каждой паре {А, т), где A eW и т = = 1, ..., М, новый символ Ат, а также переменную 1а, т, число т назовем уровнем символа Ат и переменной ?,А,т- Кроме того, нам удобно будет полагать йо = а для каждого а е V и приписывать символам из V уровень 0.
Каждому правилу г е R, содержащему в правой части вхождения вспомогательных символов, и каждому т = 2, ..., М сопоставим систему новых правил следующим образом: если г = А-> хВу, B^W, х, y^V*, то система состоит из одного правила Ат~>хВту\ если r = xByCz, В, С elF, х, у, геУ’, то система состоит из всевозможных правил вида Ат-> xBm,yCmz, где либо т1=т2 = т — 1, либо одно из чисел ти т2 равно т, а другое меньше т. Число т назовем уровнем правил построенной системы. Кроме того, каждому правилу вида А-+хВу, B^W, xy^V+, и вида А->х, xeV+, сопоставим новое правило Ах-*хВ^у, соответственно Ах->х\ этим правилам будет приписываться уровень 1. Множество всех символов (правил) уровня т будем обозначать Vm (соответственно Rm)-
Далее сопоставляем каждой паре (А, т), А е W, Щ= 1, .,., М, грамматику Гд, т = (Уо U ... U Ущ-и Ущ,
240
СЛОЖНОСТЬ ВЫВОДА В Б-ГРАММАТИКАХ [ГЛ. 7
Ат, Rm)\ число т будем называть ее уровнем. Из определения правил уровня т ясно, что все Та.ш линейны.
Поскольку L (Г) = Li U ... U LM, где Lm, т = 1, . . , .. ., М, состоит из тех цепочек из L(T), для которых существуют деревья полных выводов в Г, имеющие густоту т, нам достаточно представить в требуемом виде каждый из языков Liy . . . , LM (поскольку объединение тривиальным образом сводится к подстановке в конеч1 ный язык). Удобнее доказывать несколько более общий факт, а именно представимость в том же виде каждого
языка LAi m(A^W, т— 1..........М), состоящего из тех
цепочек х, для которых в Г существуют (А, х)-деревья густоты т.
Мы покажем, что язык LA,m можно получить следующим образом: сначала подставим в язык L{YA,m)s ^ (Vq U ••• UVm-i)* вместо каждого символа Вт>, 1^ ^т'^т—1, соответствующий язык L(YB,m'); в полученный язык (в словаре F0U ••• U 1^т_2) вместо каждого символа Ст", 1^т"^т — 2, подставим язык L{Tc,m") и т. д., пока не получим язык в словаре V0 = V. СоотЕштствующее подстановочное выражение читатель без тфуда выпишет.
1) Если цепочка х принадлежит описанному только что языку — будем обозначать его L'a, т, —то она может быть выведена из Ат с помощью новых правил уровней 1, ..., т. Устранив во всех цепочках полученного таким образом вывода индексы 1, ..., ш, мы получим, очевидно, вывод х из А в Г.
2) Включения La, m^L'A,m докажем индукцией по т.
Ясно, прежде всего, что деревья вывода густоты 1 — это в точности такие деревья, что в отвечающих им выводах используются лишь правила, содержащие в правых частях не более чем по одному вхождению вспомогательного символа; а эти правила совпадают — с точностью до индекса 1 при вспомогательных символах — с новыми правилами первого уровня. Поэтому La, i ^
Е L'a, 1 для любого Допустим, что m> I и ут-
верждение доказано для густот, меньших т. Рассмотрим (А, х)-дерево Т густоты m (А е W, хе У+). Пусть ао, ... •, at — старший путь в Т и ро, . . ., |3и (и ^ t +
+ 1) —все (упорядоченные «сверху вниз») узлы Т, под-
чиненные узлам старшего пути, не лежащие на нем ц
АКТИВНАЯ ЕМКОСТЬ
241
помеченные вспомогательными символами*) (рис. 14). Для каждого / = О, ..., и будем обозначать через Т, полное Pj-поддерево дерева Т. Положим также trij = = |я(7’3) = |л(Г, Pj); для любого / имеем mj < m.
Каждому узлу оц старшего пути отвечает некоторое правило Га = Ai —? со* грамматики Г, где Л, — метка при а; и цепочка со» содержит, если i <С t, одно или два вхождения вспомогательных
