Гладкий - Формальные грамматики и языки - 1973 (947381), страница 19
Текст из файла (страница 19)
сировано, то в каждой цепочке вь О ~ 4 -= и — 1, имеется единственная «активная точка», отвечающая «ядру» применяемого на 1+ 1-м шаге правила, т. е. такая точка, из которой в дереве Т' либо выходит более одной дуги, либо выходит одна дуга, но конец ее помечен иным символом, чем начало. Пусть эта «активиая точка» есть у4евеей; (напомним, что точка — это вхождение символа). Если на 4-м шаге применяется правило ~р4 4- ф4 4, так что в; = $4 4494 4414 4 (причем выделенное вхождение 494, «то самое»), и если при этом ~Ь-~(()х4((194-44р -4) (т.
е. «активная точка» содержится в фз,), мы будем говорить, что 4+ 1-й шаг сил ь но за це плен с йм по отношению к размеченному выводу .0' н дереву Т'. Если в НС-грамматике каждому полному выводу 0 отвечает единственное растянутое дерево Т' и при этом каждый следующий шаг 0 сильно зацеплен с предыдущим по отношению к Т' и любому соответствующему размеченному выводу 0', мы будем называть эту грамматику сильно сцепленной.
Л е м м а 3.! (о сильном сцеплении). Для любой НС-грамматики Г можно построить сильно сцепленную НС-грамматику Г', эквивалентную Г и такую, что Тг'(и) Тг (и). Чтобы убедиться в справедливости этой леммы, достаточно заметить, что построенная при доказательстве теоремы З.б грамматика Г' станет сильно сцепленной, если к правилам 3-го рода фигурирующей в ее построении грамматики Г, добавить всевозможные правила вида (а (со,))оп (вз) — ь(а(в,))о й (вт) ( и (а,))об(аз) -+ у(а,) 13(вз), у(е,) 6(а,) — ь у(в,) в„где в„аз — непустые цепочки длины, не большей 21, в основном словаре Гз и 6(вз), у(в,) — новые вспомогательные символы, а правила 4-го рода (а(е))оа-+ва заменить правилами вида (и (е,))о у (вз) -+ (а (а,)) 6 (вз), (а (а,))" 6 (вз) — ь е (е,) 6 (вз), в (е,) 6 (вз) -+ в (е,) ат, а (е,) аз -+ у (в,) в„е (в,) -+ е„ где вн вз у Означают то же, что и раньше, а 6(аз), в(в4) — новые вспомогательные символы.
При этом временная сложность грамматики, вообще говоря, возрастает, но не более чем вчетверо, так что подбором постоянной сз можно добиться выполнения нужного неравенства для временнбй сложности. 4 к4! 96 л.а а 4 А. в. Гладкий ГРАММАТИКИ СОСТАВЛЯЮЩИХ )ГЛ. 3 Введем еще следующее понятие.
Для произвольной цепочки Ге будем называть ее с е ч е н и е м любой (собственный) пустой интервал (а, р), где сс и 0 — соседние точки Го. В качестве обозначения для сечения (а, О) будет использоваться также любая пара вида (А, В), где А — отрезок ы с правым концом а и  — отрезок 4о с левым концом (1.
Пусть теперь à — сцепленная грамматика и Р= =(соо, ..., 4о„) — вывод в Г, ЯвлиющийсЯ отРезком полного вывода. Пусть Г„..., à — некоторый пересчет правил Г и д — максимум длин правых частей правил Г. ПуСтЬ даЛЕЕ ГО = Оа',Геев И ГОИ 4»," — СООтВЕтСтВЕННО ТОЧНЫЕ потомки Го' и Гооч в ви Обозначим через й,' и й," соответственно наибольший конец Го,' и наибольшее начало Го4' длины которых не превосходят д. Отрезок й',.й," назовем / й з о н о й в л и я н и я сечения (со', соил) = Л. Если В =)(а О е Ь вЂ” точка цепочки й,' и С=4)еу»0— точка цепочки й , то расстоянием точки В, соответственно С, от центра зоны будет называться число — 1 К (, соответственно(4)у((таким образом, расстояние никогда не равно нулю).
Пусть сь ..., 4р — последовательность, составленная из номеров тех шагов вывода Р, на которых «активные точки» содержатся в соответствующих зонах влияния сечения Л. Следом вывода Р на сечении Л мы назовем последовательность ((йь и,), ..., (яр, ир)), где й; — расстояние «активной точки» цепочки Го! ! от центра зоны и и; — номер правила, применяемого на шаге с номером йр Возможен и пустой след. Л е м м а 3.2 (о замещении).
Пусть Р, =(Гоо, ..., Го„) и Рн=(Оо, ..., 0 ) — выводы в сильно сцепленной НС-грамматике Г, являюи(меся отрезками полных вывогде Го', и 0' — точные предки для Го„' и О' соответственно. Если при этом след вывода Р, на сечении (Го', Гоел) совпадает со следом вьсвода Р, на сечении (6',, 0"), то из цепочки Го'Оол выводима в Г цепочка Го'„9" Д о к а з а т е л ь с т в о. Пусть ((/Гь и~) (йр, ир) )— общин след и (/4, ..., 4р) (/! у /р) соответствую- щие последовательности шагов выводов Р! и Рй. Пусть для определенности й! - О.
Тогда на шагах вывода Р4, предшествующих 4! (если такие имеются), может преобразовываться только цепочка Го'. Если при некотором / = 1, ..., р — 1 числа Йк и /сц.а имеют разные знаки, то обязательно 144! — — /4+1. Если же ка и /44+4, например, оба положительны, то между шагами /4 н 144! может преобразовываться только правая половина цепочки (т. е. потомок Го,"). То же верно и для вывода Р . Поэтому Го'„О" можно вывести из ГооО" так; сначала преобразовывать со'„как в выводе Р!, до шага 4!! затем проделать шаги, входящие в след, до первого шага — с номером 4, в Р4 и /» в Ря„— для которого числа йа н й444 имеют одинаковые знаки; затем, если, для определенности, эти числа положительны, преобразовывать правую половину цепочки О/в как в выводе Рь до шага /4+! и т.
д. Теперь мы можем перейти к основному утверждению этого параграфа. Пусть (à — словарь, аь ам Ь вЂ” элементарные символы такие, что аь ай ен (Г, Ь цй У, и пусть 4Р— фУнкЦиЯ, отобРажаюЩаЯ (аь ай)" в ЬУ*Ь и УДовлетворяющая условию (ар(х) (» с( ° (х(, где 4/ — постоянная. Положим /., =(хар(х)х(хев(а4,ай)4).
Функцию ф можно подобрать так, чтобы /.е был НС-языком (в частности, это верно при ф(х) = ЬЬ вЂ” пример 11 из $1.3 с тривиальной модификацией; дальнейшие примеры см. в упражнении 3.19). В то же время имеет место Теорема 3.7, Если /(п) — числовая функция, по порядку меньшая *) пй, то /.й ф 2'г)(НС).
Д о к а з а т е л ь с т в о. Допустим противное: пусть существует НС-грамматика Г = (У, ((У,/,)4), для которой /.(Г) = /.еи Тг(п) ~ /(и), так что 1пп Тг(п)/и'= л а =О. Будем считать — ввиду леммы 3.1 мы имеем на это право, — что Г сильно сцеплена. Введем целочисленные параметры /, п. Число / всегда будет кратно и'! будем полагать 1/п=г, //и' г/п=ф ') Говорят, что функция /(л) и о п о р я лк у м е н ь ш е д(л), если !ии / (л)/Е (л) = О. ГРАММАТИКИ СОСТАВЛЯЮЩИХ 98 !ГЛ. 3 3 гл1 ОценкА ВРеменноп слОжнОсти нс.языкОВ 99 Будем, кроме того, считать, что всегда д ) д, где д— максимум длин правых частей правил Г.
Пусть х ~ (аьа»)", ~х~ = 21. Положим у = у(х) = = хф(х)х. Представим у(х) в виде у(х) = уг(х)... ... угг м (х) (вместо у, (х) часто будем писать просто уг), где (уг~ =... = )у„~=!у ег! = ° ° = ~уггм!= г, так что, если х' и х" — соответственно левая и правая половины х, то у„+г = х"гр(х) х'. Пусть 0; = (1 = аг(х), в'(х), ..., в'(х) = у(х))— вывод у из 1 в Г, удовлетворяющий условию 3 ( ( »Гг Цу1), откуда для любого е) О при достаточно больших 1 следует (1) 3 ( В12 Для каждого 1= О, ..., з представим цепочку а е~(х) в виде е~ = а! (х) а((х) ег' (х) а1 (х) ... ВХ (х) в!, (х), где а1(х) — предок у,(х) и длина каждого а1(х) не больше единицы. Пусть 13 — наименьшее из чисел 1, для которых ~в1~,(х)~) д.
Будем различать два случая: 1) Найдутся сколь угодно большие п такие, что бесконечно много чисел 1, кратных и', удовлетворяет условию: не менее половины всех цепочек х длины 21 таковы, что как среди отрезков а('(х), ..., вь(х), так и сРеди ОтРезков вь+ (х), ..., аг~„+,(х) имеютсЯ отРезки длины, не меньшей д. (Соответствующие и и 1 будем называть допусти мыми.) 2) Для каждого достаточно большого и все достаточно большие числа 1, кратные и', таковы, что по крайней мере для половины всех цепочек х даний 21 либо длйны всех отрезков еь(х), ..., а! (х), либо длйны всех отрезков в~+2(х), ..., аг'„+,(х) меньше су. Сл уч а й 1.
Пусть 1О 12 — соответственно наибольшее из чисел 1 = 1, ..., п и наименьшее из чисел 1 = и + 2, ..., 2п + 1, удовлетворяющих условию ~вгь (х) ~ ~у для данной цепочки х. Пусть Иг — множество всех цепочек в (аь аг) длины 21 и Иг — наибольшее по мощности подмножество Иа для любых двух цепочек которого 1г и 12 соответственно совпадают. Прн достаточно больших допустимых 1 будет, очевидно, 13(Иг) ) 2ннг.
Положим п(х)=е1 (х)а1 (х)вь+, (х)а~в+,(х) ... аг (х). Ясно, что ) п(х) !(~вь(+)в~~+, ~+~вь)+ 2пд+2и„' но (е) ~, (егь! =г, (вь+,(»(у+д; посколькУ д)д и г пд, имеем (2) ~ п(х) ~( 8г. Пусть Иг — наибольшее по мощности подмножество Иь удовлетворяющее условию: если хг, хг ее Иа то п(х~) = п(х,). Б силу (2) при достаточно больших допустимых п и 1 будет 13(Иг) ) 2в"'. Общее значение п(х) для х ~ Иг обозначим Р. Начиная с этого момента, число п будем считать фиксированным, так что д и г будут расти пропорционально 1. Обозначим через 0', «хвост» вывода 12, начинающийся с вь, через 13 — произвольное сечение цепочки вг н через рА — длину следа вывода О'„ на 13.
Если 3 — множество всех сечений в!, то, очевидно, (3) р, (аз. Аез В силу (1) и (3) для любого положительного действительного числа 6 и любого целого положительного числа й при достаточно больших допустимых 1 в каждом из отрезков а,', в„'+н в(~ доля сечений, не удовлетворяющих неравенству р (б1, (4) будет не больше 11/г. Пусть и есть одно из чисел гп и+ 1, г, и ΄— множество сечений аь, принадлежащих в~ (т. е. тех сечений аь, которые являются одновременно сечениями еь). Для произвольного Ь ~5„обозначим через 1 число ггдммлтикн состдвляющих [Гл. з бзз[ оцннкд вявменнои сложности нсязыков [б[ ~д)[2(И2) (1 — — ). (5) Это сечение будем обозначать Ь1 при и=1„бг при и=и+ 1 и Ьз при и=я,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
