Формальные свойства грамматик - Хомский Н.
Скачать (прямая ссылка):
Были сделаны некоторые попытки развить систематический метод, ведущий от множества цепочек к разбиению подцепочек на типы составляющих (см., например, работы [6, 25, 26, 32]). Эти подходы, несомненно, связаны друг с другом и с рассматриваемыми здесь системами, но точная природа этой связи еще не исследована. Несколько отличный подход к систематической категоризации типов составляющих можно найти у Хнза [28].
Другой подход вытекает из теорнн семантических категорий Лес-невского, которая была развита для нужд изучения формализованных языков. Некоторая модификация этой теории, основанная на формулировке Айдукевнча [1 ], была предложена Бар-Хиллелом
12] в качестве точного аналога метода анализа по непосредственным
И. Хомский
составляющим, разрабатываемого в современной лингвистике. Лам-бек [33—35 ] также построил несколько систем в общем того же типа но с некоторыми дополнительными изменениями и исследовал вопрос об их применимости к лингвистическому материалу. Схожие подходы также имеются в работах [15, 16, 74, 77]. Здесь мы следуем изложению Бар-Хнллела, Гайфмана и Шамнра [3],
Система категорий может быть установлена следующим путем. Выберем конечное число простых категорий (например, категория s для предложений н категория п для имен и именных групп; это единственные простые категории, рассматривавшиеся в системе Айдукевнча). Простые категории суть категории. Если аир — категории, то [а/р ] (читается: «а над р») и L\p ] (читается: «а под р») также будут категориями — назовем их производными категориями. Таким образом получаются категории, такие, как In/s], Is/[n/s] 3 или [[rt\n]\[s/rt]l. Других категорий нет. Каждому элементу терминального словаря Vt присваивается одна нлн несколько категорий. Множество категорий, сопоставленных элементам Vt , вместе со списками членов этих категорий составляет
грамматику G. Имеется два правила сведения:
а) последовательность двух символов,
обозначающих категории, вида [а/p], р сводится к а, (82)
б) последовательность двух символов,
обозначающих категории, вида я, [я\р] сводится к р.
Эти правила напоминают правила сокращения дробей в арифметике, чем и были вызваны такие обозначения.
Если теперь дана цепочка х элементов Vt , заменим каждый символ из Vt в этой цепочке символом, обозначающим категорию, к которой он принадлежит, и таким образом получим последовательность символов категорий. Поскольку каждый член цепочки может принадлежать к нескольким категориям, каждой цепочке ставится в соответствие несколько последовательностей символов категорий. Обозначим эти последовательности C1(X).....С,(х). Последователь-
но применяя правила сведения к некоторой C1(X), мы получим, что либо C1(X) в конце концов Ждется к S1 либо она в конце концов сведется к некоторой последовательности одного нли более символов, отличной от s. Если, для некоторого [' С (*) сводится К S, мы говорим, что грамматика G порождает х\ если такого і нет, G не порождает х. Множество цепочек, порождаемых грамматикой G, есть язык, порождаемый G. Так же как и для других ранее обсуждавшихся порождающих грамматик, считать, что G порождает предложения, или считать, что она получает на вход цепочки н решает, являются ли они предложениями (т.е. как распознающий ме-
Формальные свойства грамматик
ханизм),— это просто вопрос терминологии. Обычно ДЛЯ ТОЛЫ*43 4To описанных категориальных грамматик употребляется второй ііз этих оборотов речи.
• Функционирование такой грамматики можно пояснить на nPli-мере. Пусть наша грамматика содержит простые категории /* и s, слова John, Магу, loves, died, is, old, very (Джон, Мэри, л*°®Чт, умер, есть, старый, очень) н следующее распределение слов І*0 Категориям: John, Mary — ви; died — в [n\sl; loves — в [itAs]/„t old — в InlnI; very — в [fi/n]/ln/nl; is — в ln\s}l[nln}. 'Гак образом, непереходный глагол (такой, как died) рассматриРае-гся как «оператор», который «превращает» имя существительное, ст^я-щее слева от него, в предложение; переходный глагол (iove.<>) Рассматривается как оператор, превращающий имя существительное, стоящее справа от него, в непереходный глагол; прилагат^ль*іое рассматривается как оператор, превращающий существительное, стоящее справа от него, в существительное; наречие very рассматривается как оператор, превращающий прилагательное, сГ0Я1Щее справа от него, в прилагательное; связка is рассматривает^ Нак оператор, превращающий прилагательное, стоящее справа оf н®го, в непереходный глагол. Цепочки, показанные ниже, сводя?ся к s следующим образом:
a) John died п [n\g]
б) John loves Mary
n, \n\s]/nt n
___~(n\»l
S
в) John is very old (83)
n. [га\я]/[п/п1, [n/n]/[n/n], [п/п]
_______________~~ "in/nT
n, [n\sj
Грамматика описанного типа называется двунаправлен но% категориальной грамматикой. Если все производные категории грам. матики имеют вид [Др ] или все имеют вид [л/fi ], эта систер'13 Называется однонаправленной категориальной грамматикой. АйДУ^евич рассматривал только второй вид категорий, поскольку он вначале занимался системами бесскобочной записи, где функторьг Предшествуют аргументам.
