Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
8*
?228 СЛОЖНОСТЬ ВЫВОДА В Б-ГРАММАТИК.АХ [ГЛ. 7
Следствие. Для любой Ъ-грамматики Г, для которой D-rin) ограничена числом k, можно, если известно k, построить эквивалентную ей линейную Ъ-грамматику.
Остается заметить, что если Г — приведенная грамматика, то Dr(n)= 1 тогда и только тогда, когда Г линейна, так что 2’с (Б) = 3 (J1) (Л — класс линейных Б-грамматик).
Металинейный язык — и даже произведение двух линейных языков — может уже удовлетворять тому условию, что для каждой порождающей его Б-грамматики ее разброс мажорирует некоторую линейную функцию.
Пример 2. Пусть L = {ambmanbn \m,n — 1,2,...}, Т = /,/?)— Б-грамматика, и L(T) = L. Как и в
примере 1, можно считать Г приведенной и не имеющей правил вида А—*В, A, fl е f. В произвольном дереве вывода Т цепочки ambmanbn из / в Г нетрудно, рассуждая аналогично примеру 1, найти два «главных пути», исходящих из одного и того же узла а (не обязательно совпадающего с корнем) и содержащих все уз^-чяы Т, помеченные циклическими символами. На этих путях для подходящих символов А, В <= W найдутся последовательности узлов аь ..., а и и Рь ...., Р/ такие, что аи ..., ah имеют метку A, a Pi, ..., Р/ — метку В, причем h, f ^ ck, где k— общее число узлов Т и с—константа, определяемая так же, как в примере 1. Обозначая через z* и и, составляющие цепочки ambmanbn, «происходящие» от at и р;- соответственно, видим, что Zi = ak‘b!i, Uj — adibei и при этом kt —
&г+1 —? li dj , Так ЧТО Ii
— /,?+1, dj — dj+1 > 0. .Поэтому в произвольном выводе, отвечающем дереву Т, найдется цепочка, содержащая вхождение подцепочки вида Л0/,_i... 0icoorj... cr/_iB, где 0j, crj Ф А (мы считаем здесь, что узлы ai, ..., ah принадлежат левому главному пути, а рь ..., Р/ — правому). Но длина этой подцепочки не меньше h-\-f^ 2> 2ck > 2с • | ambmanbn |.
[См. также упражнение 7.17].
§ 7.2. Активная емкость
Активная емкость Б-грамматик ведет себя сложнее, чем глубина и разброс. Оказывается, прежде всего,
АКТИВНАЯ ЕМКООТЬ
229
что, — в то время как все классы 5"|^Л(Б), где k — функции-константы, совпадают между собой, и то же верно для &к(Б), — разность .2^+1 (Б) — не пуста, ка-
ково бы ни было k = 1, 2, ... {S?\(Б) есть, очевидно, класс линейных языков). Это доказывается следующим примером.
Пр имер 1. Рассмотрим две бесконечные последовательности символов Ад, А\, ..., Bi, В2, ... и построим последовательность Б-грамматик Го, Гь ..., причем каждая грамматика будет иметь основной словарь {а, Ь, с, d}, вспомогательный словарь {Ло,..., Аи, Вь... ..., Bk} ({Ло} при k = 0) и начальный символ Аи, следующим образом:
I. Го = ({а, Ь, с, d}, {Ло}, Ло, {Ло —* cd} у,
II. Yh+i получается из Г^ добавлением к вспомогательному словарю символов Аи+1 и причем Л^+1
объявляется начальным символом, и к схеме — правил Au+i —* cBu+\d, Au+i * cd, Ви+\—*~йВи+\Ь, Bu+i—>аЛ»Л;-6 (*',/ = 0..../г).
Полагая L{Yk) = Lk, имеем L0 — {cd), Lk+l = = {canzbnd\n = 1, 2, ..., zeLi}ll{cd}.
Цепочки, принадлежащие языкам Lo, Lu ..., мы будем называть «гроздьями». Для каждой грозди w определим ее высоту h(w)\ h(cd) =0; если w — = camcudbmdcancvdbnd и h(cud) = i, h(cvd) — j, то h(w) = max(i, /) -f 1. Гроздь будет называться «совершенной», если в любой ее подцепочке, имеющей вид V&2, где Bi и в2 — гроздья, высоты и Уг равны.
Каждый язык Lu состоит, очевидно, в точности из всех гроздьев высоты, не большей к.
При k ^ 1 для любой грозди высоты, не превосходящей k, наименьшая активная емкость ее вывода в Г* не превосходит k. В самом деле, для Ti это тривиально; пусть доказано для Гь; любой полный вывод в Гь+i содержит цепочку вида canAiAjbnd, i, j ^ k, причем предыдущие цепочки содержат по одному вхождению вспомогательного символа, а в последующих наименьшее число вхождений вспомогательных символов получится, если сначала полностью «обработать» одно из вхождений Ai или Aj — это делается по правилам, Гг- или Г,-соответственно, — а потом другое. Итак, L* е 3?1(Б)^. •
230
СЛОЖНОСТЬ ВЫВОДА В Б ГРАММАТИКАХ
1ГЛ. 7
Установим теперь некоторые свойства гроздьев. Первые два из них очевидны:
I. В каждой грозди вхождений а равно числу вхождений Ь, а число вхождений с — числу вхождений d.
II. В любом начале грозди число вхождений b не превосходит числа вхождений а, а число вхождений d — числа вхождений с.
Следующие три свойства без труда доказываются индукцией по высоте грозди.
Назовем вхождение с в гроздь «правым», если оно непосредственно следует за вхождением d, и «левым» в противном случае.
III. В каждой грозди число левых вхождений с на единицу больше числа правых.
IV. Если гроздь содержит подцепочку cdqxcdq2... ... cdqhcd, где h ^ 2‘, то длина хотя бы одной из цепочек qu ..., qn не меньше 4 (t — 1).
V. Если cqd — подцепочка грозди, содержащая одинаковое число вхождений с и d и такая, что во всяком ее начале число вхождений d не превосходит числа вхождений с, то q содержит одинаковое число вхождений а и Ь.
Остается одно свойство:
VI. Пусть некоторую гроздь w высоты k > О можно представить в виде w = uixyzu2 таким образом, что из цепочек х и z хотя бы одна не пуста и для любого п = = 1, 2, ... цепочка wn = u\xnyznu2 также является гроздью. Тогда: а) х, у, z имеют вид х = а1, у = aiviv2b-1, z=bl, где Vi и v2 — гроздья; б) любая цепочка wn является гроздью высоты k%
