Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
Для произвольной цепочки х е9№4 представим ш/о = оо/о (л:) в виде
(0/о = Si (х) (х) Сз (х) (х),
где (?г (я), Ci+1 (х)) — Аг (/ = 1, 2, 3). Поскольку 3№4 s 3№2 и все три сечения Аь А2, Д3 принадлежат n(x), отрезки ?2 (х) и С„(х) Для всех х е ЗИ4 соответственно совпадают; будем обозначать их ?% и
Точный потомок отрезка ?,i(x) (г— 1,2, 3,4) в цепочке у{х) будет обозначаться Zi{x).
Пусть 3№5 — наибольшее по мощности подмножество 3№4, для любых двух цепочек которого хг, х2 при каждом 1= 1, 2, 3, 4 длины отрезков Zi{xx) и zt{x2) совпадают. При достаточно больших допустимых I будет ц(Ш5)^271/6. Общее значение длины zt (х) для
оценка временной сложности нс-языков
101
обозначим h., Поскольку AjeSi,, A2eS„+i, A3eS<2, имеем
<6) /„ ц<1,
(7) li + h, + h > I-
Кроме того, имеет место хотя бы одно из двух неравенств:
\(8) 1\ ~Ь h > 2?,
(8') /3 + ^4 > 2/.
Для определенности будем считать, что выполняется (8).
Пусть теперь 9№6— наибольшее по мощности подмножество 3№5> для любых двух цепочек которого хь х2 отрезки (Xi) и 2i(*2) совпадают. Очевидно, ц(Ш6)^2т~11. Общее значение z, {х) для х е 3№6 обозначим
Покажем, что в Зй6 найдутся две цепочки я, и х2 такие, что
(9) z3 (Xj) z4 (х0 ф z3 (х2) z4 (х2).
В самом деле, если х{ и х2 — различные цепочки из 3№б, то равенство
z3(xl)z4(x,) — z3 (х2) z4 (х2) = г возможно только тогда, когда /3 + Ц < 21 — 1и так что хх — z°{w'z, х2 = z\w"z,
и при этом до' Ф до". Но различных цепочек длины 21 — lx —13 — /4 имеется 2п~1'~1з~и ^ 21~1' (в силу (7)).
Поэтому в 9№6 найдется не менее 2116 цепочек х, не удо-
влетворяющих условию z3(x)z4(x) — z.
Пусть хи х2 — цепочки из Зй6, удовлетворяющие (9). Из цепочек
ffl/o (Xj) = gj (х,) ’Q%%a (x,)
®;* (^2) = ?1 (^2) (*2)
в Г выводимы соответственно цепочки
^l) = 2lZ2(^l)23^l)24^l)
и
y{x2)^z°lz2(x 2)г3(х2)г^х2).
102
ГРАММАТИКИ СОСТАВЛЯЮЩИХ
[ГЛ. 3
По лемме 3.2 из ©M*i), а значит и из /, должна быть выводима также цепочка y = z({z2(x2')z3(xl)z4(xl'). Но
в силу (8) и (9) цепочки у(х2) и у не могут одновременно принадлежать L^.
Случай 2. Пусть для определенности найдутся сколь угодно большие п такие, что бесконечно много чисел I, кратных п2, удовлетворяют условию: по крайней мере для четверти всех цепочек х длины 21 длины всех отрезков ©{«, ..., (о?° меньше q. Рассуждая совершенно аналогично случаю 1 (с очевидными упрощениями), можно для достаточно большого I найти две цепочки хх и х2 такие, что a>,0(*i) и ©^(^г) представимы в виде с»'* (*!) = ?&(*,), ю'«(*2) = ^2(*2), где
а) следы «хвостов» выводов DX}, начинающихся с со?0(*г), на сечениях ^(^г)) ПРИ * = 1 и ПРИ i = 2 одинаковы;
б) если Z[ {xt), z2 (xt) — соответственно точные потомки отрезков t,2(x^ в цепочках y(xt) (/=1, 2), то
|21(Х1)] = | г, (л:2) |= ?1, \z2{xl)\ = \z2{x2)\ = l2, причем /„ l2> I и хотя бы одно из чисел 1и 12 больше 21;
в) zt{xx) ф zi(x2) (г = 1,2).
По лемме 3.2 из co/e (Jfj), а значит и из I, должна быть выводима цепочка zx (х2) z2 (х,), которая в силу в) не может принадлежать L^ одновременно с у(х2), если li > 21, и одновременно с у (*i), если /2 > 21.
Теорема доказана.
Замечания. 1) Среди языков, удовлетворяющих условию теоремы 3.7, имеются такие, для которых доставляемая этой теоремой нижняя оценка временной сложности является точной, т. е. в принципе не может быть улучшена. Так, легко убедиться, что для грамматики примера 11 из § 1.3 временная сложность меньше п2, а по теореме 3.6 для порождаемого этой грамматикой языка можно построить и НС-грамматику не большей сложности. (Это верно и при упомянутой на стр. 97 модификации.) Другие примеры указаны в упражнении 3.19. Как уже отмечалось, примеры языков, для которых вытекающая из теоремы 3.7 оценка не является точной, неизвестны.
оценка временной сложности нс-языков
103
2) Если функция гр ни для какой постоянной d не удовлетворяет условию |i})(*) | ^ d- ] дг|, то утверждение теоремы 3.7 может не иметь места (упражнение 3.20).
Остановимся еще на классе S’n(HC) (совпадающем, в силу теоремы 3.6, с j2fc.n}(HC), где {с-п}—класс всех линейных функций). Ввиду теоремы 3.7 этот класс является собственной частью .2?(НС); с другой стороны, ондсодержит все Б-языки (см. ниже, замечание к упражнению 4.1). Естественно спросить, является ли 3? (Б) собственной частью i??(HC). Положительный ответ на этот вопрос вытекает из следующего примера.
Пример 1. Пусть Г—НС-грамматика со схемой
1->ЬАхЪ ЬАХ -*? ЬА2А2 А2А\ —^ Л2Л2Л2 АъЬ —? А3А3Ь А2А3 —*? Л3Л3Л3 ЬА3 —> ЬА^А^
Л4Л3 —>? Л4Л4Л4
Аф -> AxAxb A^Ai —? Ах Л| Л|
Л] —>? а
Очевидный подсчет показывает, что Тг (п) ^ ^2 (п — 2). В то же время Ь{Г) = [ba2ikb | k = 0, 1, ...}; в следующей главе будет доказано утверждение (следствие из теоремы 4.5), из которого непосредственно вытекает, что этот язык не является бесконтекстным.
Рассмотрим еще один пример языка, принадлежащего разности З’п (НС) — S’(Б).
Пример 2. Язык примера 10 из § 1.3 — {апЬпап\ п— 1, 2, ...} — не является Б-языком (см. ниже, § 4.3, пример 1). Покажем, как построить неукорачивающую грамматику с линейной временной сложностью, порождающую этот язык *).
