Научная литература
booksshare.net -> Добавить материал -> Лингвистика -> Гладкий А.В. -> "Формальные грамматики и языки" -> 42

Формальные грамматики и языки - Гладкий А.В.

Гладкий А.В. Формальные грамматики и языки — Москва, 1973. — 368 c.
Скачать (прямая ссылка): formalnieidialogi1973.djvu
Предыдущая << 1 .. 36 37 38 39 40 41 < 42 > 43 44 45 46 47 48 .. 136 >> Следующая

Лемма 4.3. Для всякой Ъ-грамматики можно построить эквивалентную ей стандартную бинарную Б-грамматику. Если при этом исходная грамматика удовлетворяет требованию леммы 4.2, то новую можно построить так, чтобы и она ему удовлетворяла.
Доказательство. Пусть Г = ( V, W, I, R)—Б-грамматика. В силу леммы 4.1 мы можем считать, что R не содержит правил вида А -* В, где А, В ^ W. Мы можем считать также, что каждое правило либо имеет
НЕКОТОРЫЕ ВСПОМОГАТЕЛЬНЫ^ УТВЕРЖДЕНИЯ
117
вид А -» а, где А е W, а V, либо его правая часть не содержит основных символов. Если это не так, преобразуем Г следующим образом: сопоставим каждому
деУ новый символ а, присоединим все такие символы к W, во всех правилах Г, длины правых частей которых больше единицы, заменим все вхождения основных символов вхождениями их «двойников» и присоединим к схеме Г всевозможные правила вида а—где а е V", полученная грамматика, очевидно, удовлетворяет нужному условию и эквивалентна Г. Но при выполнении перечисленных условий для получения нужного результата достаточно заменить каждое правило вида A-+BiBz ... Вь, k > 2, системой правил {Л-vjBi/7!, F]—*B2F2, ..., Fh_3 —? Bh-2Fk~2, Fk-2—*-Bh-XBh}, где Fb ... ..., Fk—2 — новые символы, разные для разных правил Г.
Займемся теперь деревьями выводов в Б-грамматиках. Заметим прежде всего, что по самому определению растянутого дерева вывода каждому размеченному выводу в Б-грамматике, начинающемуся одноэлементной цепочкой, отвечает единственное растянутое дерево, так что между такими размеченными выводами и их растянутыми деревьями имеется взаимно однозначное соответствие. Что касается собственно дерева вывода, то отвечающих ему размеченных выводов в общем случае много; мы покажем сейчас, как их можно описать.
Пусть Г = (V, W, I,R)— Б-грамматика и Т =
— (М; <(, V О W, g) — Pi-дерево, являющееся дере-
вом вывода в Г некоторой цепочки сое (V U W)* из некоторого символа B(=W. Такое /Vдерево мы будем называть (В, со)-деревом (в грамматике Г).
Расположим множество невисячих узлов Т в линейную последовательность Е\, ..., Ек так, чтобы выполнялось следующее условие: если Ej зависит от Еь то
i ^ /. Всякую последовательность невисячих узлов, удовлетворяющую этому условию, будем называть допустимой. Легко видеть, что для любого ? = 1, ..., k подграф Gi дерева (М\ -*?), образованный узлами Еi, ..., Е) и всеми соединяющими их дугами, будет поддеревом, корень которого совпадает с корнем (М; -*•). Построим теперь последовательность цепочек <oi, ... ..., сой; она будет строиться индукцией по k — i, причем одновременно с цепочкой со* будет определяться
118 Б-ГРАММАТИКИ И МАШИНЫ С МАГАЗИННОЙ ПАМЯТЬЮ [ГЛ. 4
(В, coj) -дерево = (М,; gi) такое, что его под-
дерево, образованное всеми невисячими узлами, совпадает с Gi и для каждого / <i имеет место gi{Ej) = = g(Ej). При i < k будет определяться также некоторое вхождение о» символа g'Cfi+i) в цепочку юг-. Индукция проводится следующим образом I. Полагаем ©й = и, Th = Т. II. Пусть определены ©г> ©г и Т{ (1 < удовлетворяющие сформулированным условиям. В силу допустимости последовательности Ei, ... ..., Ek узел Ei будет в дереве Gi висячим; поэтому все непосредственные потомки Ei в дереве являются в нем висячими узлами и в соответствующей этому дереву системе составляющих для ю* образуют некоторую составляющую (ранга 0 или 1). Цепочку, полученную из шi заменой этой составляющей вхождением символа g(Ei), мы обозначим юг-_1, само это вхождение обозначим а дерево, полученное из Г» выбрасыванием
всех (непосредственных) потомков Е{, обозначим TVi-Выполнение нужных условий для ©г_р ©'_[ и Точевидно. Из способа построения ац непосредственно ясно, что последовательность D = (В, ©ь ..., cofe = со) является выводом в Г, а последовательность D' — (* В *, и',..., «)^_р coft) — размеченным выводом. Индукцией' по i легко показать, что каждое Ti есть дерево вывода, отвечающее размеченному выводу (* В *, со', ...
• ••> ®г_р ©*)> так что, в частности, Т отвечает D'.
Итак, каждой допустимой последовательности невисячих узлов Т отвечает размеченный вывод D'. При этом ясно, что различным допустимым последовательностям соответствуют различные размеченные выводы. Картина будет завершена, если мы покажем, что любой размеченный вывод, отвечающий данному дереву Т, может быть получен таким способом. Чтобы убедиться в этом, рассмотрим размеченный вывод D' — (oi'0, со', ... •••> ®а_1> ®а)> где ©о = *В*, и «сожмем» соответствующее растянутое дерево Г', как описано в § 3.1. Узлами полученного дерева Т будут классы узлов Т', причем каждый класс состоит из узлов, лежащих на одном пути, и при этом каждое вхождение ©J, г = О, ..., k — 1, является «младшим» (самым далеким от корня) узлом
НЕКОТОРЫЕ ВСПОМОГАТЕЛЬНЫЕ УТВЕРЖДЕНИЯ
119
в некотором классе, отвечающем невисячему узлу Tt Если теперь обозначить через тот узел Т, для которого младший узел соответствующего класса есть ®j_lt то последовательность Еи Eh будет, как легко видеть, допустимой, и размеченный вывод, полученный по этой последовательности описанным выше способом, совпадает с D'.
Предыдущая << 1 .. 36 37 38 39 40 41 < 42 > 43 44 45 46 47 48 .. 136 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed