Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
длин левых и правых частей правил Г).
Пусть т)г — последняя цепочка вывода D', содержащая вхождение символа из Z. Шаги 1-го и 2-го рода— это все шаги с номерами, не большими г0, и только они. Для каждого /==0, 1, i0 имеем ч1г ==
где ?°, ?? е= Z0* и а es Z. Положим gt = 1?° |, h, = g—gi_v Если i-й шаг 2-го рода, то ht= 1, а если 1-го, то
— О, где е — максимум длин левых частей
правил Г. Очевидно,
io
= gi-g0 = gu.
Отсюда, обозначая через сумму ht по всем шагам рода k, получаем
т2 = s2 = ~ si < + ет,<\ ti,o | + ет{ —
= 1 Tlml + ет,<(/ + е) тх.
Доказательство закончено.
Теперь мы можем показать, что для произвольной грамматики имеется возможность «сжимать» и «ускорять» ее выводы равномерным образом в любом наперед заданном отношении, лишь бы не нарушились неравенства (1) (стр. 59); для этого, разумеется, нужно перейти к другим, эквивалентным грамматикам. Стоит заметить (см. ниже доказательства теорем 2.1, 2.2), что эти новые грамматики, вообще говоря, сложнее старой — имеют больше вспомогательных символов или
УСКОРЕНИЕ И СЖАТИЕ ВЫВОДОВ
67
правил, и сами правила могут быть длиннее, — причем усложнение грамматики оказывается тем сильнее, чем больше мы захотим упростить выводы, т. е. «сжать» или «ускорить» их. Это обычная ситуация — за простоту и удобство пользования устройством приходится платить усложнением его самого.
Теорема 2.1 (о сжатии выводов). Для любой грамматики Г и любого положительного действительного числа с можно построить грамматику Г', эквивалентную Г и такую, что
Sr(«)<raax(n, 1, cSr(n));
Tv {ti) ^ Гг (п) + max (cn, 1).
Доказательство. Пусть Г — (V, W, I, R). В силу леммы 2.2 мы можем считать, что левые части правил Г не пусты, и рассматривать только такие выводы в Г, в которых правило с пустой правой частью применяется разве что на последнем шаге.
Пусть / — натуральное число, большее 1/с и одновременно большее max |<р| и тах||ф| — |<р||. Сопо-
j? <р ф = /?
ставим каждой цепочке со е (F U К,)*, |<вК2/, взаимно однозначным образом новый символ а(оз). Множество таких символов обозначим Z.
Каждому правилу каждой цепочке
а е (F У IF)*, |co|sS^2/, содержащей вхождения <р, и каждому вхождению ? * <р * г] цепочки <р в о сопоставим правило / = /(ф, ф, 1, ti) следующим образом: если ||фг]|^2/, то / = а(со)-»а(|фг]); если же | |фг] | > 2/, то f — а (со) -> а (Ci) а (С2), где CiC2 = Stn и I ?i \ = 1 (а (?2) существует, поскольку I lipii I < 3/).
Далее, каждому правилу каждой паре
цепочек &)[, и2е(У U^)’, / <11 со, | 2/, /^|(о2|^2/,
такой, что co,co2 содержит вхождения ф, и каждому вхождению g * ф * ti цепочки ф в о^сог сопоставим правило g = g(ф, ф, ?, т], со,, <в2) следующим образом: если | | < 21 (заметим, что в любом случае | | > I), то
? = а(ю1)а(ю2)->а(|^'п); если 2/< | К 4/, то g =
=a(w1)a(co2)->a(?i)a(?2), где CiC2 = ltn и| Ci 1 = ?tn l] ([ ] — целая часть); если, наконец, | ?фг| | > 41, то g = a (о,) а (<в2) -> а (СО a (С2) а (С3), где С1С2С3 = ЕФл. I Ci Н2Л IC2I = 1 (а(Сз) существует, так как |?i|rn|<5/).
з*
68
СИГНАЛИЗИРУЮЩИЕ ФУНКЦИИ
[ГЛ. 2
Сопоставим также каждой цепочке со, |со|^2/, правило h = /г(со): а(со) —*? со.
Положим теперь Г'= (V, Z, а{1), R'), где R' состоит из всех правил f, g и h. Покажем, что Г' — нужная грамматика.
Назовем образом цепочки (V l)W)* любую цепочку 0 = a(coi) ... а((йй) такую, что g>i ... со* = % и при k> 1 для каждого / = 1, ..., k имеет место Из определения правил fug ясно, что если из цепочки %i непосредственно выводима в Г цепочка %2, то из каждого образа 01 цепочки xi будет непосредственно выводим в Г' некоторый образ цепочки %% (с помощью некоторого правила g, если |0i| > 1, и правила /, если |04| = 1). Поэтому для каждого полного вывода D = = (%0, .... Хп) в Г существует вывод D' = (0О, ... ..., 0„) в Г' такой, что 0{ есть образ х» для каждого 1 = 0.....п (в частности, 0о = а(/)); при этом в си-
лу определения образа | 0г шах (l, у| Хг |j. Из 0„
можно с помощью правил h вывести %п, причем длины промежуточных цепочек в этом выводе не будут превосходить тах(1, | Хп |) • Таким образом, мы получаем вывод Хп из a (/) в Г', в котором максимальная длина цепочки не превосходит шах(|х«1, U -г тах I Хг l). при-
V 1 о/
чем число шагов этого вывода не больше п +
+ шах^у|х«|, lj (число применений правил fug равно
п; число применений правил h не превосходит у I х« I
при |х«| 5* / и единицы при |хп| < /). В то же время — по лемме 1.1 — всякая выводимая в Г' цепочка в словаре V может быть выведена так, что сначала будут применяться правила / и g, а потом h\ отсюда ясно, что эта цепочка может быть выведена и в Г. Итак, Г7 есть нужная грамматика.
Следствие. Для любой грамматики Г и любого натурального числа k можно построить грамматику Г', эквивалентную Г и такую, что
Sr' (п) ^ шах (п, 1, Sr(n) — k)-,
Tr{n) (п) + max (я, 1).
§ 2.3]
УСКОРЕНИЕ И СЖАТИЕ ВЫВОДОВ
69
Теорема 2.2 (об ускорении выводов). Для любой грамматики Г и любого положительного действительного числа с можно построить грамматику Г', эквивалентную Г и такую, что
Гг (n) ^ max (1, сТг (п));
