Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
*) В частности, полностью замкнутым в себе сделано изложение неразрешимых алгоритмических проблем (гл. 8). Из теории алгоритмов в этом изложении используется только теорема Райса, доказательство которой приводится там же.
ПРЕДИСЛОВИЕ
пользуются, если их доказательства просты и основаны на уже «отработанной» технике. Диапазон трудности упражнений весьма широк; к некоторым из наиболее трудных и наиболее важных даны краткие указания.
Список литературы не претендует ни на какое подобие полноты; в него включены только те работы, которые упоминаются в книге, главным образом в библиографических замечаниях, также не претендующих на полный охват относящихся к делу источников.
При написании книги автор использовал свой курс лекций, изданный в свое время ротапринтным способом [Гладкий 1966]; однако имеющийся там материал составляет менее половины объема книги и излагается в существенно переработанном виде. . :
Автор рассматривает эту книгу как некоторый итог своих занятий математической лингвистикой — в особенности чтения лекций и ведения семинаров по этому предмету — в течение последних десяти лет, и ему хотелось бы упомянуть здесь о тех, кто в наибольшей степени помог ему в этих занятиях и непосредственно в работе над книгой. Прежде всего, интересы автора в теории грамматик сформировались в значительной степени под влиянием Б. А. Трахтенброта. Читатель, знакомый с его работами по теории сложности вычислений, легко поймет, в чем это влияние проявилось. Очень многим автор обязан слушателям своих лекций и участникам семинаров, их постоянному вниманию и критике; не имея возможности назвать их всех, он хотел бы особо упомянуть А. Я. Диковского, Л. С. Модину, Н. Г. Щербакову, М. К. Валиева, Р. В. Фрейвалда. Для выработки взглядов на лингвистическую сторону дела первостепенное значение имела многолетняя совместная работа с И. А. Мельчуком. Важными были замечания читателей упоминавшегося выше курса лекций, особенно М. В. Лом-ковской. В оформлении рукописи неоценимую помощь
8
ПРЕДИСЛОВИЕ
оказали автору товарищи по работе, главным образом Т. И. Шедько, Л. С. Модина и Н. Г. Щербакова. Рукопись была прочитана рядом коллег, которые высказали немало ценных. соображений и помогли устранить многие погрешности. Особенно существенными были замечания и предложения М. И. Белецкого; важные указания автор получил от М. В. Ломков-ской, Л. С. Модиной, а по приложению I — также от И. А. Мельчука и Е. В. Падучевой и по приложению II — от И. И. Ревзина. Р. Д. Равич составила предметный указатель и много помогала автору на последней стадии оформления рукописи. Л. С. Модина составила указатель обозначений. Всем этим коллегам автор выражает искреннюю признательность.
ВВЕДЕНИЕ
Когда говорят о «владении» или «умении пользоваться» тем или иным естественным языком, под этим понимают, с одной стороны, умение строить «правильные тексты» на этом языке, выражающие заданный смысл, с другой — умение определять смысл заданных «правильных текстов». При этом «правильные тексты» представляют собой последовательности .элементарных единиц из некоторого конечного набора (скажем, фонем), образованные по определенным правилам; в совокупности эти правила составляют то, что называют грамматикой языка. Сами по себе элементарные единицы никаким смыслам не соответствуют, смысл имеют только их сочетания; поэтому их внутреннее строение и материальная природа для грамматики несущественны. С аналогичной ситуацией приходится встречаться в математике: в различных ее разделах используются различные «языки», выражения которых также строятся по определенным правилам из элементарных единиц (элементарных символов); этим выражениям сопоставляются определенные смыслы, представляющие собой комбинации содержательных математических понятий. Здесь, правда, смыслы приписываются обычно и элементарным символам (например, в языке арифметики + означает сложение, 1 — единицу и т. п.), однако отсутствует какая-либо связь между «внутренним устройством» элементарного символа и природой сопоставляемого ему понятия, так что и в этом случае внутреннее строение элементарных символов несущественно и выбор их произволен*). Математические языки отличаются от естественных несравненно более простым строением, позволяющим достигать в их описании предельной четкости и однозначности; зато они столь же сильно уступают естественным языкам в широте сферы применимости.
*) Если отвлечься от таких непринципиальных соображений, как Удобство воспроизведения и запоминания, следование традиции и т. г).
10
ВВЕДЕНИЕ
В последнее время возникла особая разновидность математических языков — так называемые языки программирования, предназначенные для работы с вычислительными машинами; они, как правило, имеют более универсальную применимость и соответственно более сложное строение, чем «традиционные» математические языки, но и в том и в другом отношении весьма далеки от естественных. Так или иначе, в самых разных областях (и не только в упомянутых выше) возникают ситуации, когда приходится иметь дело с множествами выражений, построенных по определенным «грамматическим правилам» из элементарных единиц и используемых для передачи некоторых «смыслов». Представляет интерес исследование этой ситуации в общем виде, т. е. описание сбщих закономерностей строения самих грамматических правил; знание таких закономерностей позволило бы, в свою очередь, устанавливать о^щие закономерности строения образуемых по этим правилам выражений («текстов»). Именно это и является предметом теории грамматик — особой математической дисциплины, возникшей в'50-х годах нынешнего столетия. В ней строятся и изучаются формальные грамматики — абстрактные объекты, призванные служить моделями конкретных систем грамматических правил. Формальным грамматикам отвечают множества «правильно построенных выражений» — формальные языки, служащие моделями совокупностей «правильных текстов»..
