Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
§ 6.1]
КАТЕГОРИАЛЬНЫЕ ГРАММАТИКИ
191
Категории, сопоставленные символу В по пунктам
а) и б), мы будем называть левыми Б-категориями, сопоставленные по пункту в)—правыми S-категориями. (Одна и та же категория может, вообще говоря, оказаться одновременно левой и правой даже для одного и того же В.)
Функцию f мы определим так: f(a) = и г (Л).
Положим теперь G=(V, Z, Ф0, f). Покажем, что G эквивалентна Г.
Чтобы доказать включение L(r)sL(G), достаточно установить, что для всякого дерева полного вывода Г в Г найдется такое дерево сокращения Т' в G, что ц(Т') =ц(Т). Для этого, в свою очередь, достаточно убедиться в справедливости следующего утверждения: (А) Пусть D — вывод в Г, начинающийся символом / и заканчивающийся цепочкой X в словаре W, и Т — произвольное дерево этого вывода. Тогда найдется такое дерево сокращения Ti в G с пометкой Ф0 в корне, что ч(7\) есть (некоторая) цепочка, сопоставленная цепочке X с помощью функции f'.
Утверждение (А) мы докажем индукцией по числу узлов в дереве Т. Для удобства проведения индукции будем доказывать несколько более сильное предложение. Чтобы его сформулировать, введем понятие л е-вого и правого узлов бинарного дерева. Именно, если узлы а, р, у расположены следующим образом:
то мы называем узел р левым и у — правым. Кроме того, корень считается левым узлом.
Добавим теперь к (А) следующее требование: если а — левый (правый) висячий узел Т, помеченный символом В, то соответствующий висячий узел Ti должен быть помечен левой (соответственно правой) Б-катего-рией (иначе: если вхождение символа В в X отвечает левому (правому) узлу Т, то соответствующее вхождение символа в ц(Тi) должно быть вхождением левой (правой) Б-категории). Полученное таким образом предложение обозначим (А'). Докажем его.
А->а & R
• ОС
192 Дополнительные сведения о б-граммлтиках [гл. 6
I. Если Т — единичное дерево, (А') очевидно.
II. Пусть (А') доказано для деревьев, имеющих менее п узлов, и Т — дерево с п узлами (п >* 1). Рассмотрим некоторый невисячий левый узел а дерева Т, обладающий тем свойством, что в полном a-поддереве т дерева Т все левые узлы, кроме самого а, являются висячими (так что это поддерево имеет вид, показанный на рис. 12,а)); такой узел обязательно существует*),
Положим Т' = Sub (Т, т, а). Дерево Т' имеет меньше п узлов, и а — висячий левый узел Т. Если ц(Т') = X', ц(х) = Z и метка при а есть D0, то, очевидно, X и X' могут быть представлены в виде X = Y\ZY%, X'— YxDQY2. По индуктивному предположению найдется такое дерево сокращения Т\ в грамматике G, что ц(Т[) есть цепочка, сопоставляемая цепочке X' функцией и при этом для каждого вхождения символа В в X соответствующее вхождение в ц{Т\) является вхождением левой или правой S-категории в зависимости от того, какому узлу
V отвечает данное вхождение В в X'. В частности, вхождению Dq, отвечающему узлу а дерева Т‘, соответ-
*) В самом деле, если корень Р дерева Т не обладает нужным свойством, то, идя из р по правым узлам, мы непременно придем к такому узлу у (возможно, у = р), что подчиненный ему левый узел б не является в Т висячим. Если б не обладает нужным свойством, то, идя из б по правым узлам, мы опять-таки придем к такому узлу, что подчиненный ему левый узел не является в Т висячим, и т. д. Но этот процесс не может быть бесконечным.
Рис. 12.
§6.1]
КАТЕГОРИАЛЬНЫЕ ГРАММАТИКИ
193
ствует вхождение в ц(Т[) левой Оо*категории Д, отвечающее некоторому висячему узлу а' дерева Т', причем Ц(T'i) — Ui AU2, где U\ и Ьг — цепочки категорий, сопоставляемые функцией f цепочкам Ух и Уг соответственно. Пусть теперь Z = Ai ... AhB (Ai} ..., Ah,
B&W). Вхождения А\...........Ah отвечают здесь левым
узлам дерева т (а значит, и дерева Т'), вхождение В — правому узлу. Пусть, кроме того, Di, D2, Dk~i, Dk — В — метки при правых узлах т, упорядоченных сверху вниз (см. рис. 12, а)). Тогда схема R содержит правила D0—*A\D\, Z)j-»"Л2?)2, Dh-\-*-AkDh. Обозначим через т' Pi-дерево, изображенное на рис. 12,6).
Имеем ц (т') = />?“ [D?«\D2d«] ... [D*d1,\dM [d?“\A], так
что ц(г') сокращается до Л, и при этом дерево Г, = Sub (Т'и а', т') является, очевидно, деревом сокращения цепочки категорий U = U^, сверх того,
1) = ц(Т\) есть цепочка, сопоставляемая функцией f' цепочке X (поскольку ц{х') сопоставляется, как сразу видно из определения цепочке Z), и каждому вхождению символа В в X соответствует вхождение в U левой (правой) В-категории, если данное вхождение В в X отвечает левому (правому) узлу Т (действительно, для вхождений символов в Vi и это верно по индуктивному предположению, а для вхождений в Z ясно из построения). Итак, (А') доказано.
Докажем теперь включение L(G)sL(r). Аналогично предыдущему для этого достаточно установить справедливость следующего предложения:
(Б) Если для некоторой цепочки XeVf найдется дерево сокращения V в G с меткой Фо в корне такое, что ц(Т') сопоставляется цепочке X функцией f', то либо X — /, либо X выводима из / в Г.
Докажем (Б) индукцией по |Х|.
I. Если |*| = 1, то Х = 1. .
II. Пусть (Б) доказано для всех цепочек длины, меньшей п, |Х| = п(п > 1), и V — соответствующее дерево сокращения. Если узлы а, р, у дерева Т' расположены так:
