Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
= [ттш ио)=к, f4())=[T\[K\Tl]], ы=) =
= [Г\[Ф0/Г]]. Полезно также найти, аналогично предыдущему примеру, множества F(@).
Дальнейшие «абстрактные» примеры см. в упражнении 6.1. Лингвистический пример см. [Гладкий — Мельчук 1969, стр. 127—131].
Примеры 3 и 4 в какой-то степени поясняют содержательный аспект работы К-грамматик: категория, приписываемая грамматикой той или иной цепочке, отражает «синтаксическую роль» последней, причем эта роль понимается либо как принадлежность к одному из немногочисленных «основных синтаксических классов» (если приписанная категория является элементарной; так, в примере 4 основные классы — «терм», «формула», «левая скобка»), либо «операционно»: «данная цепочка есть оператор, превращающий цепочку такого-то класса в цепочку такого-то класса» (так, в примере 3 категория [Ф0/Ф1] приписывается унарному оператору ~) и цепочкам вида (21) а, синтаксически также ведущим себя, как унарные операторы, а категория [Ф)\[Фо/Ф1]] — бинарным операторам &, А, :э). Аналогичным образом можно поступать для естественных языков; например, непереходный глагол • может
*) Имеется в виду следующий вариант определения ппф:
(i) pl....pk суть ппф; (ii) если 91, S3 — ппф и a — V. то
*Т(Я) й .(Я) a (33) — ппф; (iii) других ппф нет.
5 6.1]
КАТЕГОРИАЛЬНЫЕ ГРАММАТИКИ
189
рассматриваться как оператор, переводящий существительное в предложение. Подробнее о лингвистическом аспекте К-грамматик см. [Гладкий — Мельчук 1969, стр. 122—136, 150—153].
Перейдем к вопросу о взаимоотношении между К-грамматиками и Б-грамматиками. В одну сторону этот вопрос решается чрезвычайно просто. Пусть G = = (V, W, Фо, f) — К-грамматика. Рассмотрим Б-грамма-тику Г = (V, W', Фо, R), где W' состоит из всех категорий, являющихся частями элементов значений f*), а R — из всевозможных правил следующих трех видов:
(1) W Ф[Ф\ЧЧ, где [Ф\?] е= W' (тогда иФДе W')\
(2) Т-^[Т/Ф]Ф, где [У/Ф]еГ;
(3) Ф->а, где Фе/(а).
Будем говорить, что Г канонически соответствует G. Эквивалентность G и Г, т. е. равенство L(G)= L (Г), очевидна.
Произвольное дерево вывода Т в грамматике Г мы. будем называть деревом сокращения цепочки ц(Т) в грамматике G. (Разумеется, дерево сокращения можно определить и независимо от Г.) Любой цепочке языка L(G) каждое ее дерево сокращения позволяет хорошо известным нам способом (см. § 3.1) сопоставить размеченную систему составляющих (очевидно, бинарную). В содержательном аспекте эта система обладает любопытной особенностью: среди всевозможных ее
иерархизаций естественно выделяются две «главные», наиболее важные для приложений, так что К-грамматика позволяет достаточно «хорошим» способом сопоставлять цепочкам не только системы составляющих, но и деревья подчинения (см. § П1.3). Эти иерархизации получаются так. Пусть А — неточечная составляющая* «происходящая» от узла дерева сокращения с меткой-Ф; тогда из двух непосредственно вложенных в А составляющих В, С одна — пусть В — происходит от узла с меткой [Ф/Т] или [Т\Ф], где У — метка узла, от которого происходит С. При одной из интересующих нас
*) Часть категории Ф определяется так: (а)Ф есть часть Ф; ф) если Ф = [ЧЛ©] или Ф = [’T/e], то ? и 0 — части Ф; (у) если 'F — часть Ф и 0 — часть ’Р, то 0 — часть Ф; (б) Т может быть частью Ф только в силу (а) (Р), (у).
190 ДОПОЛНИТЕЛЬНЫЕ СВЕДЕНИЯ О Б-ГРАММАТИКАХ [ГЛ. 6
иерархизаций главной составляющей будет всегда считаться С («аргумент»), при другой В («оператор»). Первую иерархизацию мы назовем прямой, вторую — обратной. Для формальных языков математической логики наиболее адекватной обычно оказывается обратная иерархизация (полезно убедиться в этом для языков примеров 3 и 4, построив для некоторых их цепочек соответствующие деревья подчинения), в то время как для естественных языков предпочтительнее прямая*). Впрочем, для последних еще удобнее может оказаться иерархизация, выбранная более сложным способом.
Возникает вопрос, для всякой ли Б-грамматики можно построить эквивалентную ей К-грамматику. Мы покажем сейчас, что этот вопрос решается положительно; более того, нужная К-грамматика может быть построена так, чтобы значения ее приписывающей функции содержали только категории вида А, [Л\В] и [Л\[В\С] ], где А, В, С — элементарные категории.
Пусть Г = (1/, W, /, R)— стандартная бинарная Б-грамматика. Построим для нее К-грамматику следующим образом:
1) Каждой упорядоченной паре (А, В), A,B^W, сопоставим новый символ А3. Положим Z' = {AB\A, B^W} и Z = Z' 1){Фо}, где Ф0фг'.
2) Чтобы определить приписывающую функцию /, введем сначала вспомогательную функцию f', отображающую W в множество конечных подмножеств K{Z), следующим образом:
а)Ф0€=П/). i
б) Если A->BC^R и D^W, то категории СА и [Л°\С°] принадлежат f' (В).
в) Если В, D^W и А —категория, сопоставленная символу D по одному из пунктов а), б), то [SD\A] ef' (В),
г) Категория может принадлежать f'(B), В е W, только в силу а), б), в).
*) Это связано прежде всего со следующим обстоятельством. Основное структурное различие между естественными и формальнологическими языками состоит в том, что в первых имеются как предикативные, так и определительные (атрибутивные) связи, тогда как во вторых — только предикативные. Но определение естественно, с одной стороны, считать подчиненным определяемому, с другой — рассматривать как оператор, действующий на определяемое (а не наоборот).
