Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
Возникнув в результате усилий, направленных на выработку точных методов описания естественного языка, теория грамматик сразу же сомкнулась, с одной стороны, с теоретической лингвистикой, которая по существу всегда занималась построением абстрактных моделей*), но не имела средств для их точного описания (что немало препятствовало ее развитию), с другой — с теорией алгоритмов и теорией автоматов, где среди прочих проблем возникает вопрос о конструктивных спо-
*) Такие элементарные понятия «школьной» грамматики, как подлежащее, сказуемое, падеж, род и т. п., представляют собой весьма абстрактные конструкции, относящиеся к фактам языка имен- ' но как модели. Осознать их абстрактный характер трудно только Н3‘38 их привычности. г v «у
ВВЕДЕНИЕ
И
собах задания множеств последовательностей символов, т. е. по существу тот самый вопрос, систематическое изучение которого составляет основное содержание теории грамматик; поэтому теория грамматик с самого начала смогла воспользоваться некоторыми понятиями и методами, выработанными в теории алгоритмов и теории автоматов.
Эти понятия и методы получили в ней своеобразную интерпретацию и были развиты в новых направлениях, однако связь и переплетение теории грамматик с теорией алгоритмов и в особенности с теорией автоматов остаются чрезвычайно сильными; по существу, теория грамматик может считаться, как и теория автоматов, специфическим ответвлением теории алгоритмов, причем во многих местах обе ветви срастаются. Это относится как к методам, так и к постановкам задач и характеру результатов.
Место теории грамматик внутри общей теории алгоритмов может быть — весьма грубо и приблизительно — охарактеризовано следующим образом: теория грамматик изучает в известных аспектах «внутреннее строение» рекурсивных множеств некоторых специальных классов, по преимуществу наиболее простых, и как раз настолько простых, что реально возникающие в математике конструкции не выводят за пределы этих классов, за исключением тех (как правило, диагональных) конструкций, которые специально предназначаются для доказательства существования сколь угодно сложных объектов.
Говоря о прикладном значении теории грамматик, следует прежде всего отметить ее приложения к лингвистике, которой формальные грамматики доставляют весьма удобный метаязык. Кроме того, они нашли широкое применение для описания упоминавшихся выше языков программирования. Кажется достаточно правдоподобным, что сфера приложений формальных грамматик, в частности в гуманитарных исследованиях, будет со временем расширяться *).
*) Имеются чрезвычайно интересные опыты использования конструкций, по существу представляющих собой формальные грамматики, в поэтике; см. «Морфологию сказки» В. Я. Проппа (1-е изд., Л., 1928; 2-е изд., «Наука», 1969), недавние работы А. К. Жолковского и Ю. К. Щеглова.
12
ВВЕДЕНИЕ
Основоположником теории формальных грамматик по праву считается американский лингвист Н. Хомский. Именно он указал на возможность использовать для описания естественных языков некоторые исчисления, рассматривавшиеся ранее в теории алгоритмов (но не игравшие там особенно существенной роли), придав им удобную для этого форму (с тех пор за такими исчислениями закрепилось данное Н. Хомским название «порождающих грамматик»); он же ввел в рассмотрение те специальные классы порождающих грамматик, которые представляют для лингвистических приложений наибольший интерес, и указал пути их использования в лингвистике (замечательно, что именно эти классы грамматик оказались связанными с упоминавшимися выше простыми классами рекурсивных множеств); наконец, он положил начало математическому исследованию формальных грамматик, введя некоторые важные для этого понятия (в частности, понятие машины с магазинной памятью) и доказав ряд основных фактов*).
Сделаем еще несколько замечаний, относящихся уже не столько к самой теории грамматик, сколько к ее изложению в настоящей книге.
1) Теория грамматик является в настоящее время настолько разветвленной дисциплиной, что было бы очень трудно собрать в одной книге все ее наиболее интересные результаты или хотя бы отразить все направления исследования. Такую задачу автор перед собой не ставил, и вряд ли это было бы целесообразно. Имелась в виду совсем другая цель, а именно: изложить основы этой теории, ее «классические» понятия и факты, а из направлений более специальных и более новых лишь некоторые, но достаточно полно и подробно — так, чтобы читатель мог не только составить представление
об общем характере теории грамматик, но и почувствовать используемые в ней методы, ее «кухню», а при наличии желания и прочих условий также и подготовиться к самостоятельной работе в этой области.
Разумеется, при выборе специальных вопросов для изложения в книге автор в значительной мере руководствовался своими личными вкусами.
*) Весьма существен также вклад Н. Хомского в собственно Лингвистику; это, однако, не относится к предмету настоящей книги.
Введение
Среди сравнительно новых разделов теории грамматик, не получивших отражения в книге, особого упоминания заслуживает «теория управления выводом», представляющаяся весьма перспективной как с теоретической, так и с прикладной точки зрения. Эта область, заслуживает, впрочем, отдельной монографии. Упомянем также об окрестностных грамматиках (некоторые косвенные сведения о них имеются в настоящей книге в § 4.5 и упражнении 5.7), А-грамматиках (также вскользь затронутых в § 4.5), оценках сложности распознавания порождаемых грамматиками языков.
