Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[19]

является срезом гнезда £, имеющим статус

1 + max{sj\1 < i < l}.

Заметим, что при работе шагов 2-3 алгоритма 3 цепочка Sqz представляет срезы 0гнезда КСвыражения (0Squeeze(())0. Заметим, что для s > 1 срез со статусом s гнезда

получается подстановкой в

(1 ground(u))1

вместо заглушек некоторых срезов со статусом, не превышающим s - 1. В частности,

(i ground(u))i является срезом гнезда (1u)1, имеющим статус 1. Пусть для любого КСвыражения £

Nests(£)

есть обозначение множества всех гнезд, встречающихся во фракциях из Clan(£).

Пусть £ есть КСвыражение, s - неотрицательное целое. Обозначим через Sections(£, s) множество всех срезов со статусом s гнезд, участвующих в Nests(£).

Вернемся к алгоритму 3. В следующей теореме, как и раньше, предполагаем, что

0 G Names(Z).

Теорема 10. Для любого неотрицательного целого s справедливо равенство

Sections((0Z)0, s) = Sections((0Squeeze(Z))0, s).

Доказательство. Индукцией по s.

При s = 0 рассматриваемое множество срезов является множеством заглушек. По определению клана множество Clan((0()0) определяется через

Trim((0 Z)0) = ATrim(().

Из конструкции шагов 1, 2 алгоритма 3 следует, что КС выражение (0Squeeze(())0 и его клан представляют все заглушки, представленные в ATrim((), и только их. Следовательно, теорема в данном случае верна.

Пусть теперь s > 0. Тогда каждый рассматриваемый срез представлен для некоторого целого l > 0 цепочкой вида

(iu)i = (iV0)(nui)nvi... (Hui)HVl)i,

ground(u) = V0(n)цVi... (M)4vh

Из конструкции алгоритма (см. процедуру Replacement) следует, что для лю -бого имени 1 G ANames(() множества

{ground(£)\(i£)i G Nests((0()0)}


{ground(0\(iOi G Nests((oSqueeze(())o)}

совпадают каждое с Embeddings(i), т.е. равны между собой. Таким образом, каждое из множеств

Sections((0Z)0, s) и Sections((0Squeeze(Z))0, s) получается (ср. замечание к определению среза) из одного и того же множества

Ut6AWames(c) [{(i} Embeddingt}]

всевозможными подстановками вместо заглушек цепочек, входящих соответственно в

U0<j<sSections((0C )0, j)

U0<j<sSections((0Squeeze(Z ))0,j). По предположению индукции

Sections((0Z )0,j) = Sections((0Squeeze(Z ))0,j)

для 0 < j < s. Значит, верно и равенство

Sections((0Z)0, s) = Sections((0Squeeze(Z))0, s)

Следствие 4. Nests((0()0) = Nests((0Squeeze(())0).

Доказательство. Заметим, что каждое гнездо С является своим срезом, т.е. принадлежит множеству Sections(C, s) для некоторого целого s > 1. Так как каждый элемент кланов интересующих нас КСвыражений является 0гнездом, неравенство

Nests((0()0) = Nests((0Squeeze(Z))0) противоречило бы теореме 10 □

Следствие 5. L((0()0) = L((0Squeeze(Z))0). Доказательство. Согласно следствию 4 верно равенство

Clan((0Z)0) = Clan((0S queeze(Z))0).

Значит, по определению задаваемого КС выражением языка имеем равенство рас сматриваемых языков □

Теорема 11. \Squeeze(()\ < \(\.

Доказательство. Положим

nZ = Ы )0\

и убедимся, что в каждый момент работы алгоритма 3 выполняется неравенство

\Sqz\ < щ.

Оно очевидно для шага 1. Действительно, запись выражения ( представляет собой непустую цепочку, поэтому на шаге 1 имеем

\Sqz\ = \(0)0\ < \(0Z)0\ = nz.


На шаге 2 значение величины Sqz изменяется процедурой Replacement. Процедура заменяет заглушки одноименными срезами статуса 1 гнезд КСвыражения

(сС )о.

Из определения среза видно, что срез образован сцеплением некоторых участков (возможно, разъединенных) соответствующего гнезда. Будем говорить, что срез покрывает этот набор участков гнезда (или КСвыражения, объемлющего гнездо). Теперь отметим очень важное в доказательстве данной теоремы обстоятельство, вытекающее из закона взаиморасположения гнезд: различные срезы единичного статуса покрывают в КС выражении наборы участков, элементы ко торых попарно не перекрываются. (Это верно и для одинаковых на вид срезов статуса 1, относящихся к различным гнездам одного и того же КС выражения. Но нас интересуют различающиеся срезы, так как только они собираются в мно жествах Embeddings.) Таким образом, гнездо можно "выложить", как мозаику, всеми срезами единичного статуса, которые извлекаются из его записи.

Процедура Replacement использует все текстуально различные срезы статуса 1. Каждый из них используется для замены заглушки ровно один раз. Следова тельно, вся совокупность цепочек, внедряемых в Sqz процедурой Replacement не может превзойти по длине КС выражения (оС)о.

По завершении шага 2 в Sqz еще могут присутствовать заглушки. Ясно, что так может быть в том и только том случае, когда какие либо различные гнезда дают одинаковые срезы со статусом 1, т.е. когда в исходном выражении дублируется некоторая информация. Чтобы остаться в пределах рассматриваемого формализма - КСвыражения, необходимо заменить оставшиеся заглушки какиминибудь из одноименных с ними гнезд. В целях укорочения КСвыражения следует выбрать самые короткие из возможных замен. Что и делается.

Шаг 4, исключающий из рассмотрения внешние скобки (с именем 0), не влияет на соотношение длин исходного и результирующего КСвыражений □

Выявим временные характеристики алгоритма 3, опираясь на соотношение (см. доказательство теоремы 11)

Sqz < щ.

Ясно, что время работы шагов 1 и 4 не зависит от входного выражения и прене брежимо мало, а время работы шагов 2 и 3 по меньшей мере линейно зависит от щ. Действительно, для построения всех используемых алгоритмом вспомогатель -ных объектов требуется линейный просмотр исходного выражения или не более длинной цепочки Sqz.

Так как гнездо и заглушка обязательно имеют в своем составе два символа: левую и правую скобки, число гнезд и заглушек в цепочке Sqz не превышает

ISqz 1 < Щ 2 < 2 .

Текст шага 3 алгоритма 3 очень краток, и кажется, что время работы шага 3 сравнительно легко оценить. Начнем с него, подготавливая соображения, полез ные и в будущем.

В случае простейшего представления цепочки Sqz шаг 3 должен затрачивать на поиск в ней последовательных вхождений заглушек время, пропорциональное ее длине. На обработку всех найденных заглушек потребуется не более половины этой длины (ср. замечание выше о числе заглушек в Sqz).



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9] [стр.10] [стр.11] [стр.12] [стр.13] [стр.14] [стр.15] [стр.16] [стр.17] [стр.18] [стр.19] [стр.20] [стр.21] [стр.22] [стр.23] [стр.24] [стр.25] [стр.26] [стр.27] [стр.28] [стр.29] [стр.30] [стр.31] [стр.32] [стр.33] [стр.34] [стр.35] [стр.36] [стр.37] [стр.38] [стр.39] [стр.40] [стр.41] [стр.42] [стр.43] [стр.44] [стр.45] [стр.46] [стр.47] [стр.48] [стр.49]