Гладкий - Формальные грамматики и языки - 1973 (947381), страница 38
Текст из файла (страница 38)
Рассмотрим Б-грамматику Г = (К [Р',Фа,)т), где йУ' состоит из всех категорий, являющихся частями элементов значений [*), а /с — из всевозможных правил следующих трех видов: (1) Ч'-«Ф[Ф[Ч"], ГдЕ [Ф)Ч1 ЕЕ )Р' (тОГда И Ф, Ч' ЕН )Р'); (2) Ч' — »[Ч'/Ф] Ф, где [Чс/Ф] ен [Р'; (3) Ф-ь а, где Ф ен [(а).
Будем говорить, что Г канонически соответствует 6. Эквивалентность 6 и,Г, т. е. равенство /. (6) = /. (Г), очевидна. Произвольное дерево вывода Т в грамматике Г мы будем называть деревом сокращения цепочки ь[(Т) в грамматике 6. (Разумеется, дерево сокращения можно определить и независимо от Г.) Любой цепочке языка й(6) каждое ее дерево сокращения позволяет хорошо известным нам способом (см, э" 3.1) сопоставить размеченную систему составляющих (очевидно, бинарную). В содержательном аспекте эта система обладает любопытной особенностью: среди всевозможных ее иерархизаций естественно выделяются две «главиые», наиболее важные для приложений, так что К-грамматика позволяет достаточно «хорошим» способом сопоставлять цепочкам не только системы составляющих, но и деревья подчинения (см.
9 П1.3). Эти иерархизации получаются так. Пусть А — неточечная составляющая, «происходящая» от узла дерева сокращения с меткой- Ф; тогда из двух непосредственно вложенных в А составляющих В, С одна — пусть  — происходит от узла с меткой [Ф/Ч'] или [Ч'[Ф], где Ч' — метка узла, от которого происходит С.
При одной из интересующих нас «) Ч а ать категории Ф определяется так: [а) Ф есть часть Ф; ф) если Ф = [Ч'!Н! кля Ф = [Ч'/Н), то Ч' к 6 — части Ф; [у) если ж — часть Ф к Ю вЂ” часть Ч', то Н вЂ” часть Ф; [б) Ч" может быть частью Ф только в салу (а) [й), (у). )9О ДОПОЛНИТЕЛЬНЫЕ СВЕДЕНИЯ О Н-ГРАММАТИКАХ (ГЛ. Е % В.(! КАТЕГОРИАЛЬНЫЕ ГРААт(БАТИКИ (9! иерархиза ций главной составляющей будет всегда считаться С ( «а ргумент» ), при другой В («опер атор» ) . Первую иерархнзацию мы назовем и р я м о й, вторую— обратной. Для формальных языков математической логики наиболее адекватной обычно оказывается обратная иерархизация (полезно убедиться в этом для языков примеров 3 и 4, построив для некоторых их цепочек соответствующие деревья подчинения), в то время как для естественных языков предпочтительнее прямая *).
Впрочем, для последних еще удобнее может оказаться иерархизация, выбранная более сложным способом. Возникает вопрос, для всякой лн Б-грамматики можно построить эквивалентную ей К-грамматику. Мы покажем сейчас, что этот вопрос решается положительно; более того, нужная К-грамматика может быть построена так, чтобы значения ее приписывающей функции содержали только категории вида А, [А(В] и [А)[В(С[ [, где А, В, С вЂ” элементарные категории. Пусть Г = (1',)т',1,)1) — стандартная бинарная Б- грамматика. Построим для нее К-грамматику следующим образом; 1) Каждой упорядоченной паре (А, В), А, В ве ят, сопоставим новый символ Ав.
Положим Я' =(Ал [ А, В ~ Щ и Я=Я'()(Фз), где Фр ф 2'. 2) Чтобы определить приписывающую функцию введем сначала вспомогательную функцию Т', отобра. жающую )зт в множество конечных подмножеств К(2), следующим образом: ) Ф 1'(1). б) Если А- ВС~Я и 0 ее))(г, то категории ОА и [Ап)СЛ[ принадлежат !" (В). в) Если В, Вен ))(т и А — категория, сопоставленная символу 1) по одному из пунктов а), б), то [Ва)А[ ~1'(В), г) Категория может принадлежать 1'(В), В ~ )Р', только в силу а), б), в).
") Это связано прежде всего со следующим обстоятельством, Основное структурное различие между естественными и формально- логическими языками состоит в том, что в первых имеютсн как предикативные, так и определительные (атрибутивные) связи, тогда как во вторых — только предикативные. Но определение естественно, с одной стороны, считать подчиненным определяемому, с другой — рассматривать как оператор, действующий на определяемое (а не наоборот) . Категории, сопоставленные символу В по пунктам а) н б), мы будем называть левыми В-категориями, сопоставленные по пункту в) — правыми В-категориями.
(Одна и та же категория может, вообще говоря, оказаться одновременно левой и правой даже для одного и гого же В.) Функцию ( мы определим так: 1(а) = О Т'(А). л.+амя Положим теперь 6 =()г, Я, Фо, !). Покажем, что б эквивалентна Г. Чтобы доказать включение 1.(Г) с: — ' 1.(6), достаточно установить, что для всякого дерева полного вывода Т в Г найдется такое дерево сокращения Т' в б, что ц(Т') = ц(Т). Для этого, в свою очередь, достаточно убедиться в справедливости следующего утверждения: (А) Пусть 0 — вывод в Г, начинающийся символом 1 и заканчивающийся цепочкой Х в словаре йр, и Т— произвольное дерево этого вывода.
Тогда найдется такое дерево сокращения Т, в б с пометкой Фо в корне, что ц(Т,) есть (некоторая) цепочка, сопоставленная цепочке Х с помощью функции 1'. Утверждение (А) мы докажем индукцией по числу узлов в дереве Т. Для удобства проведения индукции будем доказывать несколько более сильное предложение, Чтобы его сформулировать, введем понятие л ее о г о и п р а в о г о узлов бинарного дерева. Именно, если узлы а, р, у расположены следующим образом: ° ск то мы называем узел р левым и у — правым.
Кроме того, корень считается левым узлом. Добавим теперь к (А) следующее требование: если а — левый (правый) висячий узел Т, помеченный символом В, то соответствующий висячий узел Т1 должен быть помечен левой (соответственно правой) В-категорией (иначе: если вхождение символа В в Х отвечает левому (правому) узлу Т, то соответствующее вхождение символа в ц(Тг) должно быть вхождением левой (правой) В-категорни). Полученное таким образом предложение обозначим (А'). Докажем ега. 192 ДОПОЛНИТЕЛЬНЫЕ СВЕДЕНИЯ О В-ГРАММ»ТИКАХ (ГЛ.Е кАтетоРиАльные ГРАммАтики 193 1.
Если Т вЂ” единичное дерево, (А') очевидно. П. Пусть (А') доказано для деревьев, имеющих менее и узлов, и Т вЂ” дерево с и узлами (и ) 1). Рас. смотрим некоторый невисячий левый узел а дерева Т, обладающий тем свойством, что в полном а-поддереве т дерева Т все левые узлы, кроме самого а, являются висячими (так что это поддерево имеет вид, показанный на рис.
12,а)); такой узел обязательно существует*). а(3 1 б=((, дв Рис. 12. Положим Т' = БиЬ(Т, т, а). Дерево Т' имеет меньше и узлов, и а — висячий левый узел Т'. Если ц(Т')= Х', ц(т) = Л и метка при а есть Р„то, очевидно, Х и Х' могут быть представлены в виде Х = У~ЛУз, Х'= У(Роуз. По индуктивному предположению найдется такое дерево сокращения Т', в грамматике 6, что ц(Т() есть цепочка, сопоставляемая цепочке Х' функцией 1', и при этом для каждого вхождения символа В в Х соЪтветствующее вхождение в ц (Т1) является вхождением левой или правой В-категории в зависимости от того, какому узлу Т' отвечает данное вхождение В в Х'.
В частности, вхождению Ре, отвечающему узлу а дерева Т', соответ- '1 В самом деле, если корень Р дерева 1 не облалает нужным свойством, то, идя из р по правым узлам, мы непременно придем к такому узлу у (возможно, у = р), что подчиненный ему левый узел б не является в Т висячим. Если б не обладает нужным свойством, то, идя из б по правым узлам, мы опять-таки придем н такому узлу, что подчиненный ему левый узел не является в Т висячим, и т. д.
Но зтот процесс не может быть бесконечным. ствует вхождение в ц(Т() левой Ро-категории Л, отвечающее некоторому висячему узлу а' дерева Т', причем ц(Т()=У(АУз, где У( и Уз — цепочки категорий, сопоставляемые функцией 1' цепочкам У, и Уз соответственно. Пусть теперь Х = Аз ...
А»В (Аь ..., А», Вен Ч7). Вхождения А(, ..., А» отвечают здесь левым узлам дерева т (а значит, и дерева Т'), вхождение В— 'правому узлу. Пусть, кроме того, Рь Вз, ..., О» (, Р» =  — метки при правых узлах т, упорядоченных сверху вниз (см. рис. 12, а)). Тогда схема В содержит правила Ро- А,Р(, 0(- АзРМ ..., Р» (-ьА»0».
Обозначим через т' Р,-дерево, изображенное на рис. 12, б). Имеем ц(т') =0('[0~(~0з~~ 1(0»-'АР»'~(10»~"(сз~, так что ц(т') сокращается до Л, и прн этом дерево Т, = БНЬ(Т(, а', т') является, очевидно, деревом сокращения цепочки категорий У = У(ц(т') Уз, сверх того, У = ц(Т,) есть цепочка, сопоставляемая функцией цепочке Х (поскольку ц(т') сопоставляется, как сразу видно из определения 1', цепочке Х), и каждому вхождению символа В в Х соответствует вхождение в У левой (правой) В-категории, если данное вхождение В в Х отвечает левому (правому) узлу Т (действительно, для вхождений символов в У( и Уз это верно по индуктивному предположению, а для вхождений в Х ясно из пост оения). Итак, (А') доказано. г окажем теперь включение 1. (О) ы 1.
(Г). Аналогично предыдущему для этого достаточно установить справедливость следующего предложения: (Б) Если для некоторой цепочки Х ~У~( найдется дерево сокращения Т' в 0 с меткой Фо в корне такое, что ц(Т') сопоставляется цепочке Х функцией 1', то либо Х = Т, либо Х выводима из 1 в Г. Докажем (Б) индукцией по (Х!. 1. Если (Х! = 1, то Х = А . П. Пусть (Б) доказано для всех цепочек длины, меньшей и, (Х(= и(и.в 1), и Т' — соответствующее дерево сокращения.
Если узлы а, р, у дерева Т расположены так: ° се 7 А. В. Глалкиа 19» дополнитвльныв сввдиния о в-ггдммдтик»х !гл. в кдтегояидльныв ГР»им»тики г ».п !95 и Ф, Ч', 6 — метки при а, р, у соответственно, то Ч'6 непосредственно сокращается до Ф; в этом сокращении Ч" является «аргументом», а 6 — «оператором» (поскольку метки при узлах Т' не содержат символа /), так что 6 = [Ч''!Ф[, и Ч' — элементарная категория («знаменатели» всех категорий, входящих в значения /', элементарны). Таким образом, все левые узлы Т' помечены элементарными категориями, а все правые — неэлементарными. Рассмотрим невисячий узел а дереа1 ва Т' такой, что а) а — правый узел или совпадает с корнем Т'! б) в пола, ном а-поддереве т' дерева Т' все 1-'/(, правые узлы, отличные от а, висячие; Д такой узел обязательно существует (аналогично предыдущему).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
