Гладкий - Формальные грамматики и языки - 1973 (947381), страница 46
Текст из файла (страница 46)
Таким образом, х не может содержать вхождений с и й одновременно. Но если х содержит вхождения и', не содержа вхождений с, то при достаточно больших и начало и~х" цепочки и„ не будет обладать свойством П. Если же х содержит вхождения с, не содержа вхождений й, то все вхождения с в х", кроме разве одного, будут левыми; в то же время, поскольку х н г с точностью до перемены местами с и и' ведут себя одинаково, цепочка г тоже не может содержать вхождений с и и' одновременно; если она не содержит д, то уже цепочка и» будет нарушать свойство 1, а если она содержит й, не содержа с, то из нарушит свойство 1П.
Итак, х не содержит ни с, ни й, н то же, разумеется, верно для г. Отсюда сразу следует, что цепочка х не может содержать а и Ь одновременно, иначе она содержала бы вхождение аЬ или Ьа, но таких подцепочек в гроздьях нет. То же верно для г. Если теперь предположить для определенности, что х ~ Л, имеем х = а' илн х = Ь~, ! ) О. Но второе невозможно из-за нарушения свойства П для цепочки и„ при достаточно большом п.
Поэтому х = а', откуда г = Ь' ввиду свойства 1. Остается показать, что у также имеет требуемый вид, Если высота и равна 2, это очевидно. Пусть предложение доказано для всех высот, меньших й, и высота и равна й, так что и=ср!1(,уй, где р=а, д=Ь и !ь !»в гроздья высоты, не большей й — 1. Если х содержится в р и г — в д, наше утверждение очевидно; но при х, содержащемся в р, г должно содержаться в у, и обратно, иначе цепочка и» не порождалась бы грамматикой ГА. Если обе цепочки х и г содержатся в 1, илн в !ь то утверждение справедливо по индуктивному предположению.
Остается случай, когда х содержится в 1~ и г — в !м но в этом случае и» нарушала бы свойство Ч. Теперь мы перейдем к доказательству основного Утверждения: покажем, что Е +, Ф ЫА'(Б) при любом ЕЗЕ СЛО>КИОСТЬ ВЫВОДА В В-ГРАММАТИКАХ !гл. 7 АКТИВНАЯ ЕМКОСТЬ й = 1, 2„ ...
Для этого введем сначала вспомогательное понятие. «совершенного бинарного дерева порядка й» (сокращенно «й-дерева»). Именно: 1-деревом называется всякое дерево ширины 1; если для некоторого Й понятие й-дерева определено, то (й+ 1)-деревом называется всякое дерево вида где ! — дерево ширины '1 (возможно, единичное), а и Ь вЂ” дуги, 1! и 1» — й-деревья. Если в дереве Т полного вывода в Б-грамматике найдется поддерево, не содержащее висячих узлов Т и являющееся й-деревом, то во Всяком выводе, отвечающем дереву Т, имеется цепочка, содержащая не менее й вхождений вспомогательных символов. Действительно, для й = 1 это очевидно; если для неко~оро~о й утверждение справедливо, и Т содержит поддерево Т', не содержащее висячих узлов Т и являющееся (й+ 1)- деревом, то во всяком вь>воде (а>!>,...,В>,), отвечающем Т, некоторая цепочка В>! будет содержать вхождение вспомогательного символа, отвечающее корню Т', из определения (й+ 1) -дерева ясно, что некоторая цепочка мь 1) !', будет содержать два вхождения а и р вспомогательных символов, отвечающих корням двух й-деревьев; но тогда при дальнейпгем выводе наименьшее число вхождений вспомогательных символов в одну цепочку, являющихся потомками а и р, получится, если сначала полностью «обработать» а, а потом р, или наоборот, и это число в силу индуктивного предположения будет не меньше й+ 1.
Далее нам будет удобно воспользоваться еще одним вспомогательным понятием — понятием «совершенной бинарной системы отрезков (цепочки) порядка й» (сокращенно «й-системы»), которое мы определим так: 1-система состоит из одного отрезка длины, большей 1, (й+ 1)-система получается из объединения двух й-си- стем таких, что никакой отрезок одной из них не пересекается ни с каким отрезком другой, добавлением еще одного отрезка, содержащего все отрезки обеих й-систем. Ясно, что если система составляющих, отвечающая некоторому дереву Т полного вывода в Б-грамматике, содержит й-систему, то Т содержит й-дерево.
Пусть Г = (1/, )Р', 1, К) — произвольная,Б-грамматика, порождающая Т.А (й ) 1), Нам достаточно теперь доказать, что для некоторой цепочки из Т.А всякая система составляющих, сопоставляемая ей выводом в грамматике Г, содержит й-систему. При этом мы можем считать, аналогично предыдущим примерам, что Г является приведенной и не имеет правил вида А-+В, А, В ~ 1Р'. Пусть а и р — два узла некоторого дерева Т полного вывода в Г, помеченные одним и тем же символом А еп !)т и такие, что р зависит от !х.
Если о и у — составляющие, «происходящие» от к и р соответственно, то о = хдг, А )- хАЕ, откуда А ) — х"Аг" для любого п = 1, 2, ..., причем хотя бы одна из цепочек х и е не пуста. Поэтому ввиду свойства Ч! х = а>, г = Ь!, у = а!О>и»Ь>, где о! и о» вЂ” гроздья, Выберем совершенную гроздь ш высоты й так, чтобы для любой ее подцепочки х, являющейся гроздью высоты, большей О и представимой в виде х = = са" 1!1»Ь»т( (1! и 1т — гроздья), число п было не меньше 2(р+ 1) дт(Р!'>, где р — мощность )(!" и д — максимум длин правых частей правил Г.
Фиксируем некоторую систему составляющих С, сопоставляемую цепочке ш некоторым выводом в Г,— соответствующее дерево вывода обозначим Т вЂ” и рассмотрим одну из подцепочек-гроздьев цепочки кн х = си1!гто!(, где и = а, о = = Ь", 1! и 1» — гроздья. По лемме П1.1 в системе С найдется р+1 составляющих, образующих вложенную последовательность: у! ~у»-» ...:»урР! — и таких, что либо левые, либо правые концы их попарно различны и содержатся в отрезке и. Узлы а„ам ..., !Хры дерева Т, от которых «происходят» уь у,, ..., ур+! соответственно, лежат на одном пути, и по крайней мере два из них— пусть у! и уА, ) ( й,— помечены одним и тем же символом.
По предыдущему отсюда следует, что у! = а!уАЬ>, уь = а>о>о»Ь>, где оь о» вЂ” гроздья. Теперь во всяком, СЛОЖНОСТЬ ВЫВОДА В В-ГРАММАТНКАХ АКТИВН»Я ЕМКОСТЬ 5 7а1 7ГЛ. 7 случае ясно, что отрезок и содержит л ее ы й конец у», так что у» = а'"1', причем либо 1' — начало 1,1В либо !» — начало 1'. Поскольку и 171и и о7о» начинаются символом с, имеем п7 = !. Следовательно, либо 1, — начало о!, либо о, — начало 1п но никакая гроздь не может быть собственным началом другой, так что 1, = о» откуда точно так же 1» — — оь Итак, у» = а71!1,(77, Таким образом, каждой грозди х, являющейся подцепочкой 7е, отвечает составляющая у(х) = ум содержащаяся в х и содержащая всякую гроздь, являющуюся собственной подцепочкой х. Пусть теперь С' — множество всех составляющих из С, сопоставленных таким способом всевозможным подцепочкам и, являющимся .гроздьями (включая самое и!).
Ясно, что С' есть й-система. Доказательство закончено. 3 а м е ч а н и е. Все рассуждения, относящиеся к грамматике Г, очевидно, сохраняют силу для любо" Б- -грамматики, которая а) порождает все гроздья вый соты й и б) не порождает ни одной цепочки, не являющейся гроздью. Мы воспользуемся этим ниже при разборе примера 2.
Назовем Б-грамматику, активная емкость которой мажорируется константой, Б-г р а м м а т и к ой о г р а н иченной активной емкости, сокращенно Б-ОАЕ- г р а м м а т и к о й, а язык, порождаемый такой грамматикой, — ОАЕ-языком. Всякая Б-ОАЕВ-грамматика ($5.4) является Б-ОАЕ-грамматикой (причем, если 1ь(Г) = й, то 1г(п) ~ (й). Грамматики Г» примера 1 являются не только ОАЕ-, но и ОАЕВ-грамматиками; однако легко Видоизменить этот пример так, чтобы ни один из получаемых языков не был ОАЕВ-языком. Положим, например, 1.» =1.»(.а, где 1.» — — (а"(7" ~п = —, 2,...)".
Можно показать — это предоставляется читателю, — что ни один из 1.; не является ОАЕВ-языком (ср, упражнение б.27). В то же время для каждого 1.» легко построить порождающую его Б-грамматику Г» такую, что 1г! (п)=й+1; кроме того, нетрудно убедиться, опираясь на соответствующий результат, уже цмеющийся для языков 1.», что 1.' Ф.г!»(Б). Т аким образом, уже класс й."»(Б) содержит языки, ! пе являющиеся ОАЕВ-языками. (Что касается класса ,У! (Б), то он, как уже отмечалось, совпадает с классом линейных языков.) В общем случае для активной емкости можно получить более низкую верхнюю оценку, чем для глубины и разброса: имеет место Теорема 7.4.
Для любой Б-грамматики Г справедливо неравенство!г(п) ( (г — 1) ° (1од»п+ 1), где г есть макси»7ум длин проекций правых частей правил Г на вспомогательный словарь, если этот максимум не меньше двух, и г = 2 в противном случае. Д о к а з а т е л ь с т в о. Ради удобства индукции установим несколько более общий факт: если Г = (У, йГ, 1, В) — Б-грамматика, А ~ )17, х ен У' н А 1 — х, то найт дется вывод х из А в Г, активная емкость которого не превосходит (г — 1) (1ой»~х)+ 1). Ограничимся сначала случаем, когда г ~ 2, т. е. правая часть каждого правила Г содержит не более двух вхождений вспомогательных символов. (Грамматику, удовлетворяющую этому условию, мы будем называть слабо бинарной.) При 1х) = 1 утверждение очевидно. Пусть оно доказано для цепочек длины, меньшей и, и пусть ~х~ =и и11 — произвольный вывод х из А. Пусть далее ь7 — первая цепочка вывода 1), содержащая два вхождения вспомогательных символов (если такой цепочки нет, то все доказано): ь» = = 1ВиСО, В, Сея 'В7, 1, и, о е- =У*.
Тогда х= 1уиго, где В 1- у, С 1- г. При этом длина хотя бы одной из цег г почек у, г — пусть у — не превосходит п)2. По индуктивному предположению можно найти вывод 1)' цепочки у из В и вывод 0" цепочки г из С, активные емкости которых не превосходят соответственно 1од»)у)+ 1 ( =. 1ои»п и 1од»)г~+ 1 ( 1оп»п+ 1. Производя сначала все шаги вывода 0 до получения цепочки ь7, затем все шаги О' и, наконец, все шаги 1)", будем иметь вывод х из А активной емкости, не превосходящей !Од»и+ 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
