Введение в формальный анализ естественных языков - Ляпунова А.А.
Скачать (прямая ссылка):
Мы выделим три вида рекурсивных элементов, особенно важных для последующего изложения. Рекурсивный элемент А называется самовставленным, если он встречается в конфигурации типа той, которая изображена на рис. 4, а; леворекурсивным, если он встречается в конфигурации типа 4,6; праворекурсивным, если он встречается в конфигурации типа 4, в.
Таким образом, если А есть леворекурсивный элемент, то подчиненное ему дерево содержит А только в самой левой цепи (дерево, подчиненное А, — это дерево, которое может быть выведено из А); если А — праворекурсивный элемент, то подчиненное дерево содержит А только в крайней правой цепи; если
Формальный анализ естественных языков
253
А — самовставленный элемент, то подчиненное ему дерево содержит А на некоторой внутренней цепи. Эти определения нетрудно превратить в точные, однако мы будем вводить вполне точные определения только в особо интересных случаях.
Диализ рекурсивных порождающих процессов (в частности, порождающих грамматик) основан на исследованиях в области
А А А
/\ /\ /V
BC BC BC
/\/\ /\/\ /\/\
AOA Л
/\/\ /\ /\
(P)CaMoscmasntnue (d) Mteart рекурсия (а) Правая рекурсия
P и с. 4. Типы рекурсивных элементов.
оснований математики и теории доказательства. Обзор работ по этому вопросу см. в книге Дэвиса (Davis, 1958); более короткое и менее формальное введение см., например, у Роджерса (Rogers, 1959) илн у Трахтенброта (Трахтенброт, 1962), Более общее рассмотрение рекурсивных грамматик и их свойств см. в след, главе.
Мы уже говорили в этом разделе о некоторых основных свойствах грамматик и приводили примеры порождающих устройств, которые можно рассматривать как грамматики. Ниже мы попытаемся сформулировать характеристики грамматик более подробно. В разд. 4 мы опишем (более аккуратно) грамматики, в которых правила имеют внд (5), где п==1 и всякая структура является цепочкой, как в примерах (9), (10) и (13). (В следующей главе изучаются некоторые свойства таких систем.) В разд. 5 мы обратимся к более мощному классу грамматик, родственному грамматике языка Ls, предложенной в примере (12), т. е. к грамматикам, не удовлетворяющим тому условию, что в каждом правиле типа (5) структуры являются цепочками и п= 1. Наконец, в разд. 6 указываются, кратко, некоторые свойства фонологического компонента грамматики, который превращает цепочки, являющиеся выходом рекурсивного порождающего процесса, в последовательности звуков.
Мы описали порождающую грамматику G как устройство, перечисляющее определенное подмножество L множества S цепочек фиксированного словаря V и приписывающее структурные описания элементам множества L(G)1 которое мы называли
254
Н. Хамский, Дж. Миллер
языком, порожденным грамматикой С. С точки зрения того применения описываемых моделей, которое мы имеем в виду, будет более реалистично считать, что устройство G приписывает структурные «/писания всем цепочкам из 2, причем структурное описание пеночки * покачивает, и 'ійгпюсти, в каких отношениях х отклоняется от правильной построенное™, определяемой грамматикой G. Вместо того чтобы разделять S на два подмножества— L(G) (правильно построенные предложения) и L(G) (грамматически неправильные предложения),— можна считать, что G выделяет в S класс L1 абсолютно правильно построенных предложений и частично упорядочивает все остальные цепочки из 2 с точки зрения степени грамматичности. В этом случае мы говорим, что языком, порождаемым грамматикой G, является Li; «о одновременно мы допускаем, что цепочки не нз Li часто тоже могут быть поняты носителями языка* и даже поняты однозначно, притом на основе структурных описаний, приписанных им грамматикой. Цепочка из 2 П Li может оказаться понятной в результате наложения на нее интерпретации, которая основана на аналогиях и сходствах с предложениями из Li. Степень простоты и единообразия такой интерпретации предложения можно считать степенью его грамматичности. Отклонение от грамматических закономерностей — это-обычный литературный и псевдолитературный прием, и такое-отклонение отнюдь не должно приводить к непонятности; действительно, как много раз отмечалось, отступления от грамма* тических норм могут обусловливать сжатость и глубину выражения.
Определение понятия степени грамматичности на основе интерпретации не абсолютно грамматически правильных предложений и построение грамматик, приписывающих предложениям степени грамматичности, не обязательно равные нулю или единице, — все это интересные и важные задачи. Некоторые аспекты этих задач рассматриваются в работах; Chomsky, 1955, 1961 в; Ziff 1960а, 19606, 1961; Katz, 1963. Мы вернемся к этой проблеме в гл. 13. В этой и в следующей главах мы ограничимся грамматиками, которые разделяют все цепочки ровно-на две категории правильные и неправильные, и не устанавли* вают иерархию степеней грамматичности.
4. НЕКОТОРЫЙ простои класс порождающих грамматик
Мы рассмотрим здесь простой класс порождающих грамматик, которые могут быть названы грамматиками непосредствен-ных составляющих, и введем некоторые важные обозначения*
