Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
Теперь мы можем перейти к основному утверждению этого параграфа. Пусть У —словарь, а\, а2, b — элементарные символы такие, что ап Яг ^ У, b фУ, и пусть г|з — функция, отображающая {fli, а2}* в bV*b и удовлетворяющая условию |г|з(*) | ^ rf • | jc |, где d — постоянная. Положим — {лч|}(*)л:|* е {аь аг}+}- Функцию г|з можно подобрать так, чтобы Lф был НС-языком (в частности, это верно при \|i{x) = bb — пример 11 из § 1.3 с тривиальной модификацией; дальнейшие примеры см. в упражнении 3.19). В то же время имеет место
Теорема 3.7. Если f(n) — числовая функция, по порядку меньшая *) п2, то ф 3?] (НС).
Доказательство. Допустим противное: пусть существует НС-грамматика Г = (V, W, /, R), для которой ?(Г) = L*и Тг(п) ^f(n), так что Нш Гг(п)/п2 —
П-> оо
= 0. Будем считать — ввиду леммы 3.1 мы имеем на это право, — что Г сильно сцеплена.
Введем целочисленные параметры I, п. Число t всегда будет кратно п2; будем полагать //n=r, l/n2=r/n=q.
*) Говорят, что функция f(n) по порядку меньше g(n), если lim f (n)/g (п) = 0.
ОО
4 А. В. ГладкиА
98
Грамматики составляющих
[ГЛ. з
Будем, кроме того, считать, что всегда q^g, где g — максимум длин правых частей правил Г.
Пусть х^{аиа2}*, | де | = 2/. Положим у = у(х) = = х^(х)х. Представим у(х) в виде y(x)=yi(x)...
• ??y2n+i(x) (вместо у%{х) часто будем писать просто yt), где \yi\ = . .. — \уп\ = \Уп+2\ — .. . — \yzn+i\ = г, так что, если х' и х" — соответственно левая и правая половины х, то уп+i = х'г^(х)х'.
Пусть Dx= (/ = а>°(х), и1 (я)........cos(x) =у(х)) —
вывод у из / в Г, удовлетворяющий условию s ^ ^ ^г (|г/|), откуда для любого е > 0 при достаточно больших / следует
(1) S < &12.
Для каждого / = 0................. s представим цепочку
<о/ = (о/(*) в виде
со 1 = со( (ж) а{ (х) со' (х) а* (х) ... а'п (х) со'„+1 (х),
где (о{(х) — предок yt(x) и длина каждого а{(х) не больше единицы.
Пусть /о — наименьшее из чисел /, для которых
K+i(*)| >q-
Будем различать два случая:
1) Найдутся сколь угодно большие п такие, что
бесконечно много чисел /, кратных п2, удовлетворяет условию: не менее половины всех цепочек х длины 21 таковы, что как среди отрезков со{° (*), • • •, (*), так и
среди отрезков co*+2(*).......®2°„+i М имеются отрезки
длины, не меньшей q. (Соответствующие пи/ будем называть допустимыми.)
2) Для каждого достаточно большого п все доста-
точно большие числа /, кратные п2, таковы, что по крайней мере для половины всех цепочек х длины 21 либо длины всех отрезков со{°(*), • • •> ®п(х)> либо длины всех отрезков а>/»+2 (х), а>1°п+1(х) меньше q.
Случай 1. Пусть iu i2— соответственно наибольшее из чисел i = 1, я и наименьшее из чисел i = = п + 2, ..., 2п + 1, удовлетворяющих условию | (о|° (*) | ^ q для данной цепочки х.
§ 3.41 ОЦЕНКА ВРЕМЕННОЙ СЛОЖНОСТИ НС-ЯЗЫКОВ 99
Пусть 9)io — множество всех цепочек в {а.\, а2} длины 21 и 2Jii — наибольшее по мощности подмножество 90?о, для любых двух цепочек которого и и j2 соответственно совпадают. При достаточно больших допустимых I будет, очевидно, n(fflt) >2П^6.
Положим
Ясно, что | л (х) | < | to|« J +1 ®/«+J I +1 со|» | + 2nq + 2n; н0 | ®?+i I поскольку q^g и
r = nq, имеем
(2) |jt(*)|<8r.
Пусть 3Ji2 — наибольшее по мощности подмножество Ш?1, удовлетворяющее условию: если хи х2 е то n(xi) = л(х2). В силу (2) при достаточно больших допустимых п и / будет ц,(ЯЙ2) ^ 210г/6. Общее значение я(х) для х е обозначим Р.
Начиная с этого момента, число п будем считать фиксированным, так что q и г будут расти пропорционально I.
Обозначим через D'x «хвост» вывода DX) начинающийся с a>h, через А — произвольное сечение цепочки и через рд—длину следа вывода D'x на А. Если 5 — множество всех сечений то, очевидно,
(3) 2 рд <2gs.
AeS
В силу (1) и (3) для любого положительного действительного числа б и любого целого положительного числа k при достаточно больших допустимых I в каждом из отрезков cd{j, <о?°+1, со^° доля сечений, не удовлетворяющих неравенству
(4) Рд < И,
будет не больше \/k.
Пусть и есть одно из чисел г'1( n+ 1, г2 и Sa — множество сечений со/о, принадлежащих со?> (т. е. тех сечений а1*, которые являются одновременно сечениями (о?“). Для произвольного А е Su обозначим через /д число
4*
100
ГРАММАТИКИ СОСТАВЛЯЮЩИХ
[ГЛ. 3
цепочек, принадлежащих 9№2, для которых при данном А выполняется (4); число сечений, принадлежащих 5„, для которых (4) выполняется при фиксированной цепочке х, будет обозначаться gx. Очевидно, 2 /д = 2 ёх- Но
Д еSu хтщ
для любой цепочки х ^Ш2 имеем gx^ц,(5„) • 11 — .
Поэтому в Su найдется хотя бы одно сечение Д, для которого
(6) /4>»№)-(1—9-
Это сечение будем обозначать Д, при « = /,, Д2 при и = п + 1 и Д3 при и = п2.
Пусть Ш3 — подмножество Ш2, состоящее из всех цепочек, для которых каждое из сечений Ди Д2) Д3 удовлетворяет условию (4). Из (5) следует, что при достаточно больших допустимых I будет ц (З№3) ^ 29г/6-Пусть теперь 3ft4 — наибольшее по мощности подмножество 9Й3, для любых двух цепочек которого х1г х2 следы вывода D'Xl на сечениях Дь Д2, А3 соответственно совпадают со следами вывода DXl на этих сечениях. В силу (4) при достаточно больших допустимых I будет [л(2К4)>28г/6.
