Гладкий - Формальные грамматики и языки - 1973 (947381), страница 45
Текст из файла (страница 45)
Покажем прежде всего, что ни из какого символа А ен Я7 не может быть выводима цепочка вида фВфСУ, где В и С вЂ” циклические вспомогательные символы. Действительно, в противном случае мы имели бы А ! — хВуСг, В 1- итВим С ! — о»Сит, где х, у, г, иь иг, оь и» ен У", и1и» Ф Л чь в1о» Кроме того, 11-11А1ь В ! — Г, С [ — з, где 1ь 1», Г, а~У». Но тогда 11-1»хитВи»Уо»Сотхг» и г,хи,ти,уо~зотг1» = а"Ь" для подходящего и. Поэтому либо и1ги, состоит только из а, либо о1зот — только из Ь; и если, например, справедливо первое, то оказывается невозможным 1,хи1ги,'уи,го,гт, еи Ь, что по предыдущему должно иметь место.
Пусть теперь Т вЂ” произвольное дерево вывода ценочки а"Ь" из 1 в Г. Из предыдущего следует, что, каковы бы ни были два пути в Т, идущих из корня в узлы, помеченные циклическими символами, один из них является продолжением другого. Наибольший из таких путей назовем главным. Никакое поддерево с корнем в произвольном узле а главного пути, состоящее из всех узлов, зависящий от и и не входящих в главный путь, не содержит узлов, помеченных циклическими символами, так что высота такого поддерева не превосходит числа р = !»()Р), и поэтому оно содержит не более д = 1+ д+ у'+...
+у» узлов, где д — максимум длин правых частей правил Г. Следовательно, главный путь содержит ье менее Ь/(у+ 1) узлов, где Ь вЂ” общее число узлов дерева Т. Далее для подходящего символа А ен )Р найдется последовательность аь ..., а» узлов, лежащих на главном пути, упорядоченных «сверху вниз» и помеченных этим символом, такая, что для каждого т' = О, ..., Ь вЂ” 1 длина пути из ат в ат+1 не 1 превышает р, откуда Ь ) сй, где с= — —, и тем бор(е 4- т! ' лее Ь ) с 2п; важно заметить, что с — константа, не зависящая от и и от Т.
Обозначим через г~ составляющую цепочки а"Ь", «происходящую» от аь Рассуждениями, аналогичными использованным в начале разбора примера, без всякого труда устанавливается, что для любого ! = 1, ..., Ь ». с. будет хт-— -а 'Ь ', причем Ьт — Ь,+, — 1, — 1,+, для всех т = 1, ..., Ь вЂ” 1. Поэтому, во всяком случае, !т — 1т ы > О. Пусть теперь (1= мр, ьт„..., ьт = а"Ь") — произвольный вывод, отвечающий деРевУ Т, и вй, ..., ьтт» — те его цепочки, которые «проходят» через а„..., а» соответственно.
Если в цепочках ай н ьтт выделить те вхот+! ждения А, которые отвечают узлам ат и ат+, соответственно, то мы получим вй —— $АГЬ мй, — — Б'ьАОт)', где $ )-$', т! 1-т!', А )-ЬАО; при этом О =,м Л, поскольку О 1-ЬЬ Ь+1ФЛ. Следовательно, цепочка ьт» будет содержать подцепочку вида АО„,О„» ... О„где все От непусты, так что левая глубина этой цепочки, а значит, и всего вывода не меньше Ь ) с 2п. Таким образом, '9гг(п) ксп. [См.
также упражнение 7.2.) Для правой глубины картина такая же, как для левой, с точностью до обращения. Разброс, Нетрудно видеть, что роль, которую по отношению к глубине играют А-языки, по отношению к разбросу принадлежит линейным языкам, Именно, справедлива Теорем а 7.3. Для любой Б-грамматики Г и любого натурального числа Ь множество ь» (Г) является лип нейным языком. Более того, для всякой Б-грамматики Г и всякого натурального Ь можно построить линейную Б-грамматику, порождаюитую 1.»Г (Г). Дока з а т е л ь с т в о. Пусть Г = ( У, ))Г, 1, 1т ). Определим новые символы а(ьт), как в доказательстве теоремы 7.2. Каждой четверке (ф,тр,х,у), где фен(У0%')', треп(У())У)*, х, у~ У', [ф[, [ф[< Ь и ф~хтру, сопог ставим новое правило а(ф)- ха(тр)у, если фФЛ, и а(ф)- ху, если т[т = Л.
Положим Г' = (У, (Р', а(1), )т'), где Ят' состоит из всех новых символов и )т' — из всех новых правил. Эквивалентность Г и Г' очевидна, з» 228 слож»юсть ВМВОдл В Б ГРАммдтикдх [Гл. т 229 АКТИВНАЯ ВМКООТЪ д»л[ С л е д с т в и е.
Для любой Б-грамматики Г, для которой Эг(п) ограничена числом П, можно, если известно Ь, построить эквивалентную ей линейную Б-грамматику. Остается заметить, что если à — приведенная грамматика, то Ог(п) = 1 тогда и только тогда, когда Г линейна, так что Ыс(Б)=Ы(Л) (Л вЂ” класс линейных Б-грамматик). Ыеталинейный язык — и даже произведение двух линейных языков — может уже удовлетворять тому условию, что для каждой порождающей его Б-грамматики ее разброс мажорнрует некоторую линейную функцию.
Пример 2. Пусть Е = (а Ь'"а"Ь" [п»,а = 1,2, 'Г = ((2,'йТ,Е)т) — Б-грамматика, и Е(Г) = Е. Как и в примере 1, можно считать Г приведенной н не имеющей правил вида А- В, А, В~ 1(т. В произвольном дереве вывода Т цепочки а~Ь а«Ь" из 7 в Г нетрудно, рассуждая аналогично примеру 1, найти два «главных пути», исходящих из одного и того же узла а (не обязательно совпадающего с корнем) и содержащих все узлы Т, помеченные циклическими символами. На этих путях для подходящих символов А, В еп Ук' найдутся последовательности узлов а», ..., ал и р», ..., р[ такие, что аь ..., ал имеют метку А, а О„..., р[ — метку В, причем 6, 1 ) сй, где й — общее число узлов Т и с — константа, определяемая так же, как в примере 1. Обозначая через г» и и, составляющие цепочки а"'Ь'"а"Ь, «происходящие» от а; и р[ соответственно, видим, что г, = а »Ь », и[ — — а [Ь [ н при этом й»вЂ” е « — й,+, — — 1; — !»»„йз — [1;+» = е, — е,эь так по .— 1[э», йз — й;+» ' О.
1.4»этому в произвольном выводе, отвечающем дереву Т, найдется цепочка, содержащая вхождение надцепочки вида АОл»...О»ь»о»...О[»В, где Оь о, ~ Л (мы считаем здесь, что узлы а», ..., ал принадлежат левому главному пути, а р», ..., р[ — правому). Но длина этой подцепочки не меньше Ь + 1 ~ ) 2сй ) 2с [а"'Ь"'а"Ь"! (См. также упражнение 7.17). 2 7.2. Активная емкость Активная емкость Б-грамматик ведет себя сложнее, чем глубина и разброс. Оказывается, прежде всего, мл что, — в то время как все классы Ыд (Б), где й — функин-константы, совпадают между собой, и то же верно и »» для 3'да(Б), — разность 2'2.2»(Б) — Ы'д(Б) не пуста, каково бы ни было А=1, 2, ...
(У»(Б)'есть, очевидно, класс линейных языков). Это доказывается следующим примером. Пример 1. Рассмотрим две бесконечные последовательности символов Аь, А», ..., В», Вм ... и построим последовательность Б-грамматик Гь, Г», ..., причем каждая грамматика будет иметь основной словарь (а,Ь,с,й), вспомогательный словарь (Аь,,АмВН ...,Вд) ((Ао) при й = 0) и начальный символ Ад, следующим образом: 1. Гь = ((а, Ь, с, й), (Аь), А,, (А,— сй) ); 11.' Где, получается из Гд добавлением к вспомогательному словарю символов А»„» и Вдэ», причем Ал+» объявляется начальным символом, и к схеме — правил Ад+»- сВд.»й, Ад+»- сй, Вд+,-»-аВ»+»Ь, Вдэ»-д аА»А[Ь Полагая 1.
(Гд) = Ед, имеем Еь — (сй), Ед+, =(са"гЬ"й/[и = 1, 2, ..., з яЕА) () (сй). Цепочки, принадлежащие языкам 1, Е», ..., Мы будем называть «гроздьями». Для каждой грозди а» определим ее высоту Ь(ш): й(сй) = 0; если ш = = са 'сийЬ йса"сойЬ й и Ь(сий) = », Ь(сой) =1, то Ь(п») = шах(»,1)+ 1. Гроздь будет называться «совершенной», если в любой ее надцепочке, имеющей вид О»ОМ где О, и Оз — гроздья, высоты о» и оз равны. Каждый язык Ед состоит, очевидно, в точности из всех гроздьев высоты, не большей й.
П и й ) 1 для любой грозди высоты, не превосхори дящей й, наименьшая активная емкость ее вывод авГ евосходит й. В самом деле, для Г» это тривиально; Г сопусть доказано для Гд, любой полный вывод в д+» содержит цепочку вида са"А;А,Ь"й, 1, 1( й, причем предыдущие цепочки содержат по одному вхождению вспомогателыюго символа, а в последующих наименьшее число вхождений вспомогательных символов получится, если сначала полностью «обработать» одно из вхожде.- ний А, или А; — это делается по правилам, Г» нлн Г» соответственно,— а потом другое.
Итак, Еда= 1сд(Б)., Активнхя емкость 22! А тд! 230 СЛОЖНОСТЬ ВЫВОДА В Б ГРАММАТНКАХ ггл, 7 Установим теперь некоторые свойства гроздьев. Первые два нз них очевидны: 1. В каждой грозди вхождений а равно числу вхождений Ь, а число вхождений с — числу вхождений й. П. В любом начале грозди число вхождений Ь нс превосходит числа вхождений а, а число вхождений й — числа вхождений с. Следующие три свойства без труда доказываются индукцией по высоте грозди. Назовем вхождение с в гроздь «правым», если оно непосредственно следует за вхождением и', и «левым» в противном случае.
Ш. В каждой грозди число левых вхождений с на единицу больше числа правых. 1Ч. Если гроздь содержит подцепочку сдд~сйдя... ... сйуьсй, где Ь ) 2', то длина хотя бы одной из цепочек уь ..., уА не меньше 4(! — 1). Ч. Если суп' — подцепочка грозди, содержащая одинаковое число вхождений с и и' и такая, что во всяком ее начале число вхождений й не превосходит числа вхождений с, то д содержит одинаковое число вхождений а н Ь. Остается одно свойство: Ч1. Пусть некоторую гроздь и высоты й ) О можно представить в виде и = и,хугиз таким образом, что из цепочек х и г хотя бы одна не пуста и для любого и = = 1, 2, ... цепочка и„= и1х"уг" и» также является гроздью, Тогда: а) х, у, г имеют внд .к = а', у = а'01озЬ~, г = Ь', где и, и пз — гроздья; б) любая цепочка и„является гроздью высоты й.
Поскольку б) следует из а) непосредственно, достаточно доказать а). Допустим сначала, что х содержит вхождения с и д, Тогда возможны два случая: 1) некоторое вхождение с предшествует в х некоторому вхождению й; 2) все вхождения с следуют за всеми вхождениями д.
Случай 1. Рассмотрим последнее нз тех вхождений с в х, за которыми следуют какие-либо вхождения й в х, и первое из вхождений й в х, следующих за этим вхождением с. Ясно, что интервал, ограниченный этими вхождениями, пуст, так что х = гак(з, откуда х" = = г(спзг)"-'сйз, причем и может быть сколь угодно большим. Но это противоречит свойству 1Ч. Случай 2. Рассмотрев последнее вхождение с и первое вхождение и' в х, представляем х в виде г1сг, = = з,йзм где г» и з, не содержат с и к(; отсюда х' = = г1сг»з~йзм а поскольку х» — подцепочка грозди, г» н з, пусты. Далее рассуждаем, как в случае 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
