Гладкий - Формальные грамматики и языки - 1973 (947381), страница 48

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 48)

Удобнее доказывать несколько более общий факт, а именно представимость в том же виде каждого языка (.л, (А~(У, т=!, ..., М), состоящего из тех цепочек х, для которых в Г существуют (А, х)-деревья густоты и. йбы покажем, что язык 1.л можно получить слсдующим образом: сначала подставим в язык В(ГА ) = ~(Уо() ()У вЂ”,)" вместо каждого символа В, 1~( ~ (т'=- и — 1, соответствующий язык 1. (ГВ, ); в полученный язык (в словаре Уе() ...

()У 2) вместо каждого символа С ., 1 «.= т" - т — 2, подставим язык 1. (Гс;) и т. д., пока не получим язык в словаре У, = У. Соответствующее подстановочное выражение читатель без т)зуда выпишет. 1) Если цепочка х принадлежит описанному только что языку — будем обозначать его 1.'А,, — то она может быть выведена из А с помощью новых правил уровней 1, ..., т, Устранив во всех цепочках полученного таким образом вывода индексы 1, ..., т, мы получим, очевидно, вывод х из А в Г.

2) Включения Т.л „~ 1.'л докажем индукцией по т. Ясно, прежде всего, что деревья вывода густоты 1— это в точности такие деревья, что в отвечающих им выводах используются лишь правила, содержащие в правых частях не более чем по одному вхождению вспомогательного символа; а эти правила совпадают — с точностью до индекса 1 при вспомогательных символах —, с новыми правилами первого уровня. Поэтому 1.л ~ ~ = 1,А ~ для любого А е= (Уг. Допустим, что т ) 1 и утверждение доказано для густот, меньших т. Рассмотрим (А, х)-дерево Т густоты т (А ен Ю', хя Ую).

Пусть аю, ..., аю — старший путь в Т и рю,, рн (и ( 1+ + 1) — все (упорядоченные «сверху вниз») узлы Т, подчиненные узлам старшего пути, не лежащие на нем и )уи Г)ь.ю ') Каждому нз узлов аю,, аю ~ может быть подчинен самое большее один узел, помеченный вспомогзтельным снмволом н ВЧ лежзщнй нв старшем пути; для аю таких узлов ровно два. помеченные вспомогательными символами*) (рис.

14). Для каждого 1 = О, ..., и будем обозначать через Ту полное йю-поддерево дерева Т. Положим также и, = = )ь(Т!) = )2(Т, й,); для любого 1 имеем т; ( и!. Каждому узлу а! старшего пути отвечает некоторое правило г, = А; — ен грамматики Г, где Аз — метка при а; н цепочка шз содержит, если ((1, одно или два вхождения вспомогательных символов (один из них является меткой при аььь а другой, а, если он имеется,— 'меткой при А некотором рь 1 ( 1), а если аю,б, 1= ! — точно два вхождения аю (янляющиеся метками при и б„). Обозначим через. правило, которое получится из гь если прнписать левой части индекс т, а в правой части; а) при 1(1 приписать Рнс. 14.

тому вхождению вспомогательного символа, которое отвечает узлу аььь индекс т, а вхождению, отвечающему узлу )41 (если оно есть), индекс т;, б) при 1= 1 приписать каждому из двух вхождений вспомогательных символов индекс т — 1 (заметим, что т,=т„= и — 1). Очевидно, все го 1= =1, ..., 1, — правила грамматики Гл Среди отвечающих дереву Т выводов имеется такой, в котором на первых 1+ 1 шагах применяются правила (в этом порядке) и притом как раз в точках, соответствующих узлам аю, ..., аь После выполнения этих шагов получается цепочка ш, содермсащая и+ 1 вхождений вспомогательных символов, а именно символов, являющихся метками при йз, ..., р„.

Заменяя в ш каждое вхождение вспомогательного символа Вн>, отвечающее узлу бь вхождением символа В, по- п> лучим цепочку ш', которая, очевидно, получается из А«ч ю г последовательным применением правил го, гн ..., г! и, следовательно, принадлежит 1. (Гл,,„). Но цепочка х 242 СЛОЖНОСТЬ ВЫВОДА В В-ГРАММАТИКАХ [Гл. т 4 та[ степень ГнездОВАния и ОАмрвстАВления 243 получается из ат, а значит и из ат', заменой каждого вхождения вспомогательного символа, отвечающего узлу ()ь на цепочкУ г; = Ц(Тз); а посколькУ Т; есть (В[п, г[)- дерево густоты пт/ < и, имеем г[ ~ /.'И[ .

Однако язык, ° »ср получающийся нз /. (ГА ) подстановкой языков /В вместо символов В, и' < пт, — это н есть /.л 3 а м е ч а н и е. В настоящем параграфе, как и во всей главе, мы ограничились случаем Б- (а не ОБ-) грамматик, чтобы избежать дополнительного усложнения рассуждений, дающего не слишком большой выиг рыш в общности. Однако соответствующие обобщения могут быть сделаны без труда. 8 7.3. Степень гнездования и степень самовставлеиия В 3 3.1 мы ввели НС-сигнализирующие — специфические характеристики сложности вывода в НС-грамматиках, при определении которых существенным образом используется представление вывода в виде дерева. Там же были определены три конкретных типа НС-сигнализирующих: У[л, Уг и Фг. Для Б-грамматик, как мы видел» в $ 7.1, функции Уг и Уг совпадают, с точностью л и до аддитивной постоянной, с левой и правой глубиной соответственно.

Нам остается изучить (для случая Б-грамматик) поведение функции Фг (и), которую мы будем называть степенью гнездования грамма- ., тики Г. Параллельно с ней мы будем рассматривать другую функцию — степень самовставления (обозначение: Хг (и) ), — определяемую следующим образом: (1) назовем гнездо, содержащееся в системе составляющих, отвечающей дереву вывода в Б-грамматике, однородным, если все входящие в него составляющие «происходят» от узлов с одинаковыми метками (причем, если какая-нибудь составляющая «происходит» от нескольких узлов, то достаточно, чтобы один из них имел нужную метку); (В) степенью самовставления дерева полного вывода Т в Б-грамматике Г (обозначенне: ![(Г, Т) ) назовем наибольшую глубину однородного гнезда, содержащегося в отвечающей Т системе составляющих; (ш) для произвольной цепочки х ен /,(Г) по- ложим х (Г, х) = ппп т[(Г, Т) где минимум берется по всем деревьям вывода цепочки х из начального символа в Г; (1и) наконец, Хг(п)= гпах Х(Г, х).

к~С[Г[; [к[<а Из определений ясно, что Хг (и) ( Фг (и). В то же время, если р — мощность вспомогательного словаря Г, то во всяком гнезде глубины, не меньшей рп, содержащемся в отвечающей дереву вывода в Г системе составляющих, будет содержаться, в свою очередь, однородное гнездо глубины, не меньшей и; поэтому Фг (и) ( ( рХг (и). Как было уже замечено (стр. 84), Фг(п)(~ т1п(Уг (и), Уг (п)). Поэтому из теоремы 7.1 и ее аналога для правой глубины' следует, что для Б-грамматик Фг(п) (( (гп1п(9г(п), фг(п))+е — 1 где е — максимум длин цепочек х в основном словаре Г, для которых в Г имеются правила вида А — » хО или А-» Ох, причем 04= Л *). В частности, для стандартной бинарной Б-грамматики Фг (и) ( пнп (ср/г (и), стагги (и)) — 1.

В силу определения гнезда имеем (для любой НС ! грамматики) Фг(п)» (— (и — 1); это неравенство может переходить в равенство уже для линейных грамматик (например: (1- а/а, 1-+ а) ). Для любой Б-грамматики Г и любого действительного числа с, О ( с ( 1, можно построить Б-грамматику Г', эквивалентную Гитакую, что (для достаточно больших и) Фг (и)( сп (в силу аналогичного факта для левой глубины, стр.

225). Вместе с тем даже для линейного языка может оказаться, чтостепень гнездования (а значит, н степень самовставления) каждой порождающей его Б-грамматики мажорирует некоторую линейную функцию, В частности, это верно для языка примера 1 из $ 7.1, Действительно, мы можем, как и в этом примере, ограничиться приведенными грамматиками без правил вида А — В, А, В ен [Ут (ни устранение таких правил, ни переход к приведенной грамматике не меняют степеней гнездования деревьев ю~):стсс )с„»,,„„„„„, с„,„,,„, „...нс. грамматик — см упражнение 35 а) степень гнездоВАниЯ и сАмОВстАВления Р4з 4 7.3! 244 СЛОЖНОСТЬ ВЫВОДА В Е-ГРАММАТИКАХ 1гл.

т что при любом и для всякого дерева вывода цепочки а»Ь" соответствующая система составляющих будет содержать последовательность составляющих г», ..., Еь такую, что: а) й ) с 2п, где с — константа, зависящая только от грамматики; б) г» = а 15 1, причем й! — я;+! = = 1; — 1141» О для всех 1= 1, ..., /1 — 1. Однако нз условия б) вытекает, что данная последовательность является гнездом. Теперь пам остается исследовать строение множеств Еь (Г) и ЕА (Г) (смысл этих обозначений ясен по ана- Ф х логии с введенными на стр.

61). Картина здесь сходна с той, которая была получена для глубины: имеет место Теорема 7.6. Для любой Б-грал»матики Г и любого натурального числа й множества ЕА (Г) и ЕА (Г) ' являются А-языками. Более того, для всякой Б-грамматики Г и всякого натурального й можно построить А- грал»матики, порождающие ЕА (Г) и 1» (Г) соответственно. Ф х Доказательству предпошлем лемму. Будем называть вспомогательный символ А Б-грамматики Г с а м ов с т а в л я ю щ и м с я, если имеются такие непустые це- ' почки $ и»1, что А «-ЕА»1. Б-грамматику, у которой нет г самовставляющихся символов, назовем Б - г р а м м а т икойлбез с а монета вл е н и я.

йуемм а 7.3, Для всякой Б-грамматики без самовставления можно построить эквивалентную ей А-грамматику. Дока з а тельство. Пусть Г = ()л, )«',1,Е) — Б- грамматика без самовставления н р = «»()Р'). Каков бы ни был символ А ~%', из А не могут быть одновременно выводимы цепочки вида $А и Апь где е Ф Л, т« ~ ВАЛ; и если, например, А «-5А, е Ф Л, то Е не содер. г жит вхождений А. Поэтому, в частности, если р = 1, т.

е, «Р" = (1), то Г является либо праеосторонней, либо левосторонней линейной грамматикой, и можно построить эквивалентную ей автоматную грамматику (стр. 169). ПустЬ утверждение доказано для грамматик с менее чем р вспомогательными символами. Пусть для определенности 1« не содержит правил вида 1- Ц, ' 5 Ф Л. Сопоставим каждому символу А ее )Р' новый символ А и положим (У = (А ~А ее )У").

Положим далее АЛУ, 1 АПУ, 1 ,«с, 1 1' О,, 11 — 1. ВЛН, »ЕС, 141 ЕС, 1~-!))ПН, 1 л Г = (11 '»)()Р— (1)), »«,1,17), где Г7 состоит из всевозможных правил вида А- »рВ таких,что А — »рВ ее 17, и правил вида 1- »р таких, что 1- »)»ее Й и»р не содержит вхождений 1..

Характеристики

Список файлов книги