Гладкий - Формальные грамматики и языки - 1973 (947381), страница 47
Текст из файла (страница 47)
Доказательство для общего случая получается теперь из следующего почти очевидного замечания: заменив в произвольной Б-грамматике Г = (У, %7,1,11) каждое правило А- г»В7г!В»г»... г, 7В,г„где В7, ..., В, ~ еи 1(7; гь, ..., г, еи У*, э ) 2, системой правил А— -~г»В,Е,С!, С!-+В»г,С7» ..., С, »-»-В, »г, »С„ь С, » -+В, !г, !В,г., где С» ..., С, » — новые символы йзв сложность выводА в в гьлммлтиклх 1гл.
2 4 2.2! АКТИВНАЯ ЕМКОСТЬ 23У ( разные для разных правил), мы получим слабо бинарную грамматику 1", эквивалентную Г и такую, что ~г (а) ~ ~(г 1) ' ~г' (а). Оценка, доставляемая только что доказанной теоремой, не может быть поннжена (во всяком случае, по порядку): существуют Б-языки, пе порождаемые никакими Б-грамматиками с активной емкостью, растущей медленнее логарифмическая функции (и тем более не являющиеся ОАЕ-языками). Приведем пример.
Пример 2. Положим Е= Ц Е„где ЕА — язьпси 'примера 1. Язык Е порождается Б-грамматикой со схемой (1- сАа', 1-+ей, А- аАЬ, А — аПЬ). Пусть Г = = (У, Ю', ЕЯ) — произвольная порождающая Е Б-грамматика, р — мощность Ж' и д — максимум длин правых частей правил Г. Можно считать Г, подобно предыдущему, приведенной н не имеющей правил вида А — В, А, В ен )ч'. Как и в примере 1, мы можем утверждать (см. замечание на стр. 234), что если цепочка св ен ЕА, Ь > 1, выбрана так, чтобы для любой ее подцепочки х, являющейся гроздью высоты, большей О: х = = са 12126"й (гс и 12 — гроздья), число п было не меньше 2(р+1) дг~гьо, то активная емкость вывода ш из Т в Г не может быть меньше Ь. Обозначив через 1 нанменьш нменьую длину цепочки из Еы удовлетворяющей указанному условию,и полагая 4(р+ 1) угсг+о+ 2 = Ь, имеем 1, = = Ь+ 4, 1222 = 21 + Ь, откуда при Ь > 2 получается '12 = (2' — 1)(А,-!- 22.2' ( 22+' (Ь + 1), так что Ь > 1од2 12— — !Одг(Ь+!) — 1.
Поэтому для бесконечного числа значений л (именно, а = 1ь 12, .) справедливо неравенство 1г(а) > 1ойзп — 1ой2(Ь + 1) — 1, так что во всяком случае отношение 1г(п)/1оцзл не может стремиться к пределу, меньшему единицы, Более того, можно найти такую постоянную с, что Уг (и) >!Одз л — с. Действительно, при любом Ь = 2, 3, ... имеем, во всяком случае, 12чч ( 2'12, где г = 1оа2(Ь + 2); поэтому прн 12 ~ а ( 1Ае, получаем 1г(л) >Тг (12) > 1022 12 1ОЯ2 (Ь + 1) 1 > > !Оьг(12,„) — г — 1оь2(Ь+1) — 1 > > 1оига т 1032(Ь+ 1) 1 ° В заключение параграфа мы укажем характеристику ОАЕ-языков в алгебраических терминах, сходнусо с полученной в й 5.4 для ОАЕВ-языков. Для этого введем одно новое понятие, представляющее и самостоятельный интерес.
Пусть Т вЂ” конечное дерево. Сопоставим каждому его узлу а натуральное число !2(Т,а), которое будем называть г у с т о т о й этого у з л а, следующим образом. 1. Густота висячего узла равна нулю. П. Пусть для всех узлов рь ..., р„подчиненных узлу а, числа р(Т, рс), ..., р(Т, (1,) определены; тогда: а) если !2(Т,(!1) =... = !2(Т,~,) = О, то !2(Т,а)= 1; б) если шах р(Т, рс) = и - О, то: б1) в случае, когда существует только одно 1= 1, ..., з, для которого !2(Т, Рс) = = и, полагаем 12(Т, сс) = и; 62) в противном случае и(Т, а) = и+!. Далее, густотой дерева Т (обозначение: !2(Т)) будем называть густоту его корня. Из определения ясно, что в дереве густоты и все узлы, имеющие ту же густоту и, образуют путь (возможно, нулевой длины), исходящий из корня.
Мы будем называть этот пчть с т а о ш и м. Лемма 7.2. Если Т вЂ” дерево полного вывода в слабо бинарной Ъ-гр мматике, то наименьшая активная емкость вывода, отвечаюсчего этому дереву, Равна густоте Т. Д о к а з а т е л ь с т в о.
Ради удобства индукции бу« дем проводить его для любых (А, х)-деревьев, где А— вспомогательный символ и х — цепочка основных символов. Для дерева высоты 1 утверждение очевидно. Пусть оно доказано для деревьев высоты, меньшей и, и пусть высота Т равна и, а густота равна и. Если среди узлов, подчиненных корню Т, только один помечен вспомогательным символом и Т' — полное поддерево Т с корнем в этом узле, то наименьшая активная емкость выводов, отвечающих Т, будет такова же, как для выводов, отвечающих Т', а последняя равна р(Т') = и. Пусть имеются два узла, подчиненных корню Т и помеченных вспомогательными символами, и пусть Т; 1" — полные поддеревья Т с корнями в этих узлах.
Возможны два случая: а) р(Т') = 12(Т") = и — 1; б) густота одного из деревьев Т', Т" — пусть Т' — равна и, а 239 Актиаихя ЕмКОСть 21л1 2ЗВ СЛОЖИОСТЬ ВЫВОДА В Б-ГРАММАТИКАХ (ГЛ. 2 густота второго меньше п2. В обоих случаях наименьшая активная емкость вывода, отвечающего Т, получится, если сначала выполнить вывод наименьшей активной емкости, отвечающий Т", а потом — отвечающий Т' (впрочем, в случае а) можно и в обратном порядке); и в обоих случаях в силу индуктивного предположения получится вывод активной емкости и. Перейдем теперь к алгебраической характеристике ОАЕ-языков.
Эту характеристику можно сформулировать очень просто: класс ОАЕ-языков совпадает с замыканием класса линейных Б-языков относительно подстановки. Мы, однако, постараемся уточнить формулировку так, чтобы она стала эффективной. Для этого введем следующее определение. Будем называть подстановочным выражением от (переменных) $2, ..., Б всякое выражение, составленное из абстрактных символов 5„..., В„с помощью знаков подстановки (в обозначениях подстаиовок должны участвовать также некоторые элементарные символы, причем каждой переменной, выступающей в роли языка, в которой производится подстановка, сопоставляется определенный набор элементарных символов; ср. определение центрально-подстановочного выражения, являющееся частным случаем настоящего определения, на стр.
177). Например, если $2, ..., $2 — переменные и а, Ь, с, й, е — элементарные символы, то 5(Б2; а, Ь, с1ВВ Я(В2, а, Ь, с1$2, $2, Вь), 3(В2; Ь, й, е1 5(В2; а1В!!), (й), (е))) — подстановочное выражение; переменным $2, 5! и В! здесь сопоставлены наборы (а, Ь, с), (Ь, й, е) и (а) соответственно. Обычным способом определим также представление языка с помощью подстановочного выражения. Т еор ем а 7.5. а) Для любого подсгановочного выражения й'(В2, ..., $ ) и любых и линейных Б-грамматик Г2, ..., Г можно построить Б-ОАЕ-грамматику, порождающую язык Я(!.(Г!),...., А'.(Г„)). б) Для любой Б-ОАЕ-грамматики Г можно, если известно число, мажорирующее Тг(п), построить подстановочное выражение й(Б2, ..., $„) и линейные Б-грамматики Г2, ...
..., Г„такие, что Л(Г) = 6()-(Г!), ..., ( (Гь)) ° Д о к а з а т е л ь с т в о. а) Достаточно показать, что по любым Б-ОАЕ-грамматикам Г, Г2, ..., Г. можно оить Б ОАЕ грамматику порождающую язык этом Тг (и) ( й, 1г. (и) ~ (й! (! = 1,..., В), то, положив Г' = (У () ° () У, )Р () ЯУ! () " , 1 В()И () ... ()11), где )т получается из )т ..., а заменой во всех ех правилах всех вхождений а„ ..., но на уо ..., Т, соответственно, будем иметь, очевид ( й + (й, ... й ) — 1. В то же время ясно, что Г' по ождает нужный язык. = (У %', А)т) — Б-грамматика такая, что О азатель (г (п) ~ М. Замечание, сделанное в конце д ства теоремы 7А, позволяет при соответствующем уве- М считать Г слабо бинарной, так что М буд ет личении считать е евьев полных выво- также верхней границей густот дер в дов в Г (лемма 7.2).
Можно также считать, что в Г нет правил в д н а А - В, А, В еп 'и!. —, ..., М, новый символ А, а также пе емен =1,...,,н ; число и назовем уровнем симво ла А и пе,емеиКроме того, нам удобно будет полагать а, = а для каждого а ~ и при писывать символам и У уровень О. Каждому правилу г ~ )т, содержащ у р ем в п авой части вхождения в спомогательных символов, н каждому х п авил сле- п! = 2, ..., М сопоставим систему новых пр ли К =А-+хВу, В ~ ЯУ, х, у ~У'„ то система состоит из одного правила — эх у; из всевозможных правил вида -+ либо и, = пьг = т — 1, либо одно из чисел т„т2 гое меньше пт.
Число и назовем уров- правил построенной системы. ро , В еп Яг, ху ~У+, и вида д ому правилу вида А-> хВу, В еп , ху А- , х ~ У , сопоставим новое правило ! !у, А- хВ соответственно А, — х; этим прави я овень 1. Множество всех символов (пра- писываться уровень У (соответственно 1г ). Вил) уровня п2 будем обозначать с Далее сопоставляем каждо р й па е,А, п2), т. = 1, ..., М, грамматику ГА, = (Уо()... ()У -2, ьн 24! 240 СЛОЖНОСТЬ ВЫВОДА В В.ГРАММАТИКАХ !Гл.
7 АКТИВНАЯ ЕМКОСТЬ 4 1.21 А, )х' ); число и будем называть ее уровнем. Из определения правил уровня т ясно, что нсе Гл, линейны. Поскольку В(Г) = (.з ()... () 1 м, где 1,, т = 1, ... ..., М, состоит из тех цепочек из 1.(Г), для которых существуют деревья полных выводов В Г, имеющие густоту и, нам достаточно представить в требуемом виде каждый из языков (.ь . , (.м (поскольку объединение тривиальным образом сводится к подстановке в конечный язык).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
