Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
Поскольку б) следует из а) непосредственно, достаточно доказать а).
Допустим сначала, что х содержит вхождения с и d. Тогда возможны два случая: 1) некоторое вхождение с предшествует в х некоторому вхождению d\ 2) все вхождения с следуют за всеми вхождениями d.
Случай 1. Рассмотрим последнее из тех вхождений с в х, за которыми следуют какие-либо вхождения d в х, и первое из вхождений d в х, следующих за этим вхождением с. Ясно, что интервал, ограниченный этими вхождениями, пуст, так что х = reds, откуда хп =
АКТИВНАЯ EMKOCfb
231
= r(cdsr)n~xcds, причем n может быть сколь угодно большим. Но это противоречит свойству IV.
Случай 2. Рассмотрев последнее вхождение с и первое вхождение d в х, представляем х в виде г\сг2 = = Sids2, где г2 и S] не содержат end; отсюда х2 — = rxcr2s\ds2, а поскольку х2 — подцепочка грозди, г2 и Sj пусты. Далее рассуждаем, как в случае 1.
Таким образом, х не может содержать вхождений cad одновременно. Но если х содержит вхождения d, не содержа вхождений с, то при достаточно больших п начало щхп цепочки wn не будет обладать свойством II. Если же х содержит вхождения с, не содержа вхождений d, то все вхождения с в хп, кроме разве одного, будут левыми; в то же время, поскольку х и г с точностью до перемены местами cud ведут себя одинаково, цепочка z тоже не может содержать вхождений cud одновременно; если она не содержит d, то уже цепочка w2 будет нарушать свойство I, а если она содержит d, не содержа с, то w2 нарушит свойство III.
Итак, х не содержит ни с, ни d, и то же, разумеется, верно для z. Отсюда сразу следует, что цепочка х не может содержать а и Ь одновременно, иначе она содержала бы вхождение ab или Ьа, но таких подцепочек в гроздьях нет. То же верно для z. Если теперь предположить для определенности, что х Ф Л, имеем х = а1 или х—Ь1, I > 0. Но второе невозможно из-за нарушения свойства II для цепочки wn при достаточно большом п. Поэтому х = а1, откуда z = Ь1 ввиду свойства I. Остается показать, что у также имеет требуемый вид. Если высота w равна 2, это очевидно. Пусть предложение доказано для всех высот, меньших k, и высота w равна k, так что w = cpt\t2qd, где р = ат, q = Ьт и tu t2 — гроздья высоты, не большей k — 1. Если х содержится в р и г — в q, наше утверждение очевидно; но при х, содержащемся в р, z должно содержаться в q, и обратно, иначе цепочка ш2 не порождалась бы грамматикой Гй. Если обе цепочки х и z содержатся в tt или в 4, то утверждение справедливо по индуктивному предположению. Остается случай, когда х содержится в/(Иг — в t2; но в этом случае w2 нарушала бы свойство V.
Теперь мы перейдем к доказательству основного утверждения: покажем, что Ьк+1 ф 9?!к (Б) при любом
232
сложность вывода в 6-Грамматиках
[ГЛ. 7
ft = 1, 2, ... Для этого введем сначала вспомогательное понятие «совершенного бинарного дерева порядка ft» (сокращенно «ft-дерева»). Именно: 1-деревом называется всякое дерево ширины 1; если для некоторого k понятие ft-дерева определено, то (ft + 1)-деревом называется всякое дерево вида
где t — дерево ширины '1 (возможно, единичное), а и Ь — дуги, U и h — ft-деревья.
Если в дереве Т полного вывода в Б-грамматике найдется поддерево, не содержащее висячих узлов Т и являющееся ft-деревом, то во всяком выводе, отвечающем дереву Т, имеется цепочка, содержащая не менее k вхождений вспомогательных символов. Действительно, для ft = 1 это очевидно; если для некоторого ft утверждение справедливо, и Т содержит поддерево Т', не содержащее висячих узлов Т и являющееся (k-j-1)-деревом, то во всяком выводе (ооо,..., oos), отвечающем Г, некоторая цепочка со* будет содержать вхождение вспомогательного символа, отвечающее корню Т'\ из определения (ft + 1)-дерева ясно, что некоторая цепочка a>j, j > i, будет содержать два вхождения аир вспомогательных символов, отвечающих корням двух ft-деревьев; но тогда при дальнейшем выводе наименьшее число вхождений вспомогательных символов в одну цепочку, -являющихся потомками аир, получится, если сначала полностью «обработать» а, а потом р, или наоборот, и это число в силу индуктивного предположения будет не меньше ft -f 1.
Далее нам будет удобно воспользоваться еще одним вспомогательным понятием — понятием «совершенной бинарной системы отрезков (цепочки) порядка ft» (сокращенно «ft-системы»), которое мы определим так: 1-система состоит из одного отрезка длины, большей 1, (ft + 1)-система получается из объединения двух ft-си-
t
§ 7.2]
АКТИВНАЯ ЕМКОСТЬ
233
стем таких, что никакой отрезок одной из них не пересекается ни с каким отрезком другой, добавлением еще одного отрезка, содержащего все отрезки обеих ^-систем. Ясно, что если система составляющих, отвечающая некоторому дереву Т полного вывода в Б-грамматике, содержит ft-систему, то Т содержит ft-дерево.
Пусть Г = (V, W, /, R) — произвольная ^-грамматика, порождающая _ Lh (ft^l). Нам достаточно теперь доказать, что для некоторой цепочки из Lk всякая система составляющих, сопоставляемая ей выводом в грамматике Г, содержит ft-систему. При этом мы можем считать, аналогично предыдущим примерам, что Г является приведенной и не имеет правил вида А—>В, А, B<=W.
