Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
Лемма 4.10. Для любой Б-грамматики Г = = (V, W, I, R) и любого словаря Z ? V можно построить Ъ-грамматику, порождающую язык Пр^МГ) — {А}.
Доказательство. В силу леммы 4.3 мы можем считать, что Г — стандартная бинарная Б-грамма-тика. Назовем символ Л е W исчезающим, если он не является (V — Z)-бесплодным. Положим Г'= = (Z, W, I, Ri U R2), где Ri получается из R изъятием правил вида Л —*? a, a^Z, a R2 состоит из всевозможных правил вида А-* В таких, что для некоторого исчезающего символа С схема R содержит правило А-+ВС или А -* СВ. Покажем, что Г' — нужная грамматика,
s 4.2] РАСПОЗНАВАНИЕ ПУСТОТЫ И КОНЕЧНОСТИ Б-ЯЗЫКА 125
а) Пусть ^еЦГ'). Тогда, заменив в произвольном выводе цепочки х из / в Г' каждое применение правила вида А —»? В, А, В s W, применением соответствующего правила А—*ВС или А-+СВ, мы получим вывод в Г, заканчивающийся некоторой цепочкой вида л^С^Сг • •• ... xtCtXt+1, где Ci, ..., Ct — исчезающие символы и х\ ... xt+i = х. Из нее, в свою очередь, можно вывести в Г цепочку вида х^и^щ ... xtutxi+u где щ, ..., e(V — Z)*; но проекция такой цепочки на Z есть х. Итак, хеПргМГ), а поскольку A^L(r'), имеем также х е npz L(t) — {Л}, б) Пусть л;еПр2/,(Г)—{Л}. Рассмотрим цепочку г/е?(Г) такую, что Upzy = x, и дерево Т некоторого вывода цепочки у в Г. Выбросим из Т все узлы, обладающие тем свойством, что все «последние потомки» данного узла А (т. е. потомки, являющиеся висячими узлами) помечены символами из V — Z, но среди «последних потомков» узла, подчиняющего А, некоторые помечены символами из Z, а также всех потомков узлов, обладающих этим свойством. Ясно, что, во-первых, при этом будут выброшены все те и только те узлы, среди «последних потомков» которых ни один не помечен символом из Z, а поэтому на висячих узлах полученного дерева будет «написана» в точности цепочка х\ во-вторых, полученное дерево будет деревом некоторого полного вывода в Г'. Итак, ^еЦГ').
Выведем из доказанной леммы следующее любопытное утверждение.
Будем называть грамматику T={V,W,I,R) обобщенной Б-г р а м м а т и к о й (ОБ-г р а м м а т и к о й), если каждое ее правило имеет вид Л—*(о, где А е W, coe(VU№)*. Язык, порождаемый ОБ-грамматикой, будем называть ОБ-я з ы к о м.
Теорема 4.3. Для всякой ОЪ-грамматики Г можно построить Ъ-грамматику Г' такую, что/. (Г') =L (Г)— {Л}.
Доказательство. Добавив к основному словарю V\ ОБ-грамматики Г новый символ с и заменив каждое правило вида А—?Л правилом А~*с, получим Б-грамматику Гс такую, что Пру/.(ГС)= /-(Г). Остается воспользоваться леммой 4.10.
(Полезно сравнить эту теорему с результатом упражнения 3.18.)
Из теоремы 4.3 вместе с леммой 4.2 получаем
126 Б-ГРАММАТИКИ И МАШИНЫ С МАГАЗИННОЙ ПАМЯТЬЮ [ГЛ. 4
Следствие. Для всякой ОЪ-грамматики Г можно построить эквивалентную ей ОЪ-грамматику Г' такую, что правые части ее правил не содержат начального символа и всякое ее правило, левая часть которого отлична от начального символа, имеет непустую правую часть.
Теорема 4.4. Гомоморфный образ любого ОЪ-язы-ка есть ОЪ-язык. При этом для любой ОЪ-грамматики с основным словарем {аь ..., ап} и любых п цепочек у и ..., уп в произвольном словаре Z можно построить ОЪ-грамматику, порождающую язык г]з(1,(Г)), где ?ф — гомоморфное отображение, определяемое условием vKai)= У и i=l. •••. п.
Доказательство. Пусть Г = ({ai, ..., а„}, W, /, R). Без ограничения общности можно считать, что
({fl!...ап) U W)f]Z=0. Положим Г'=(2, W [){а........
..., ап}, I, R U {dj~*уи ..., ап~+уп}). Г' есть ОБ-грам-матика, и L(Y') =1])(?(Г)).
Полезно заметить, что понятие дерева вывода! можно естественным образом распространить на случай ОБ-грамматики. Именно, рассмотрим произвольное дерево вывода цепочки у из символа В в грамматике Гс, использованной в доказательстве теоремы 4.3, и устраним из него все висячие узлы, помеченные символом с. Всякое полученное так Ргдерево будет, по определению, деревом вывода цепочки Пру# из В в Г (V — основной словарь Г). Можно было бы определить дерево вывода и прямо по выводу в ОБ-грамматике (и даже в ОНС-грамматике — см. упражнение 3.18), непосредственно обобщив определение из § 3.1; это предоставляется читателю. Висячие узлы с нетерминальными *) метками будут тогда соответствовать точкам применения правил вида А-*-К (для произвольных ОНС-грамматик — правил вида %Аг\ -*?г|).
Очевидным образом распространяется на ОБ-грамматики и понятие однозначности (см. стр. 83).
§ 4.3. Необходимые условия бесконтекстности
Когда нужно доказать, что тот или иной язык не является бесконтекстным, часто оказывается полезной следующая
*) См. сноску **1 на стр. 27.
§ 4.31 НЕОБХОДИМЫЕ УСЛОВИЯ БЕСКОНТЕКСТНОСТИ [27
Теорема 4.5. Для любого бесконечного Б-языка L найдутся такие натуральные числа г и s, эффективно определяемые по порождающей L Ъ-грамматике, что любая цепочка w е L, длина которой больше г, может быть представлена в виде
(1) w = xlylzy2x2,
где: (а) уху2 Ф А; (б) | i/iZJ/2 s; (в) при любом л=1, 2, ... цепочка wn = x{y"zy"x2 принадлежит L.
Доказательство. Покажем сначала, что если Г=(У, W,I,R)—Б-грамматика без правил вида А—*В, А, В е W, то для любой цепочки юеЦГ) такой, что ни одно ее дерево вывода не может быть простым, имеется представление вида (1), удовлетворяющее условиям (а) и (в), а также условию: (б') для некоторого символа Aef существует (Л,yxzy2)-дерево, высота которого не превосходит |а (W7) -|- 1. Действительно, пусть w — цепочка, обладающая указанным свойством, Т — какое-либо ее дерево вывода и С — индуцируемая этим деревом система составляющих для w. В дереве Т найдутся два различных узла аир, помеченных одним и тем же вспомогательным символом Л и таких, что из а в р идет путь. Обозначим составляющие системы С, происходящие от узлов аир, — точнее, отвечающие им подцепочки w — через и и z соответственно. Для подходящих цепочек хи х2, уп у2 имеем, очевидно, и = yxzy2, w = хфх2 = XiyiZy2X2. Если U' и U" — соответственно полные а- и p-поддеревья Т, то V есть (Л, и) -дерево и U" есть (Л, z) -дерево. Положим U\ = U', V2 = = Sub(UUU",U'), Us=Sub(U2,U",U') и т. д. Для каждого п—1, 2, ... Un является, очевидно, (Л, yfzyf). деревом. Поэтому дерево Т„ = Sub(r, U', Un) есть (/, лг,г/^г/^л:2)-дерево, т. е. дерево вывода цепочки x]y^zy2x2 в Г. Мы получили, таким образом, представление цепочки w в виде (1), удовлетворяющее условию (в). Выполнение условия (а) вытекает из того, что Г не имеет правил вида А—* В, А, В 6f. Что касается условия (б'), то оно будет выполняться, если V' — квазипростое дерево (лемма 4.5). Если U' — не квазипростое дерево, то в нем найдутся два различных узла а\ и рь отличных от корня, помеченных одним и тем же
