Гинзбург Сеймур. Математическая теория контекстно-свободных языков (1970 р.)
В книге достаточно полно изложены основные понятия и результаты теории контекстно-свободных грамматик и языков, прослеживаются ее связи с теорией автоматов, языками программирования, лингвистикой и машинным переводом. Имеется .большое число упражнений самой различной трудности, которые в совокупности существенно дополняют основной текст книги. Книга окажется полезной математику, желающему детально ознакомиться с теорией формальных грамматик и ее связями с другими математическими теориями.
ПРЕДИСЛОВИЕ АВТОРА
Понятие контекстно-свободного языка было впервые введено в 1959 году Хомским [Хо 3] при попытке найти приемлемую математическую модель естественных языков, таких, как английский, французский и т. д. В 1959—1960 гг. появилось еще несколько работ, развивающих теорию контекстно-свободных языков [Хо 3, 4; ХМ; BGS; BPS]. В 1960 году было обнаружено, что класс так называемых «языков типа АЛГОЛ», т. е. языков, определяемых нормальной формой Бэкуса (которая представляет собой метаязык, предназначенный для описания широко распространенного языка программирования АЛГОЛ-60), совпадает с классом контекстно-свободных языков. С этого времени началось бурное развитие теоретических исследований по контекстно-свободным языкам. Значительной участие в этой работе приняли специалисты по использованию вычислительных машин для исследования естественных языков и Специалисты по языкам программирования. Контекстно-свободными языками занялись также математики и логики, которых заинтересовали соответствующие задачи, методы и результаты. Был получен ряд теоретических результатов, связанных с математическим обеспечением машин и в особенности с техникой программирования. Имеется, например, характеристика контекстно-свободных языков в терминах автоматов с магазинной памятью (специальных устройств, используемых для синтаксического анализа). Известно также, что конечный преобразователь (простейшее преобразующее устройство) отображает контекстно-свободный язык на контекстно-свободный язык. Другим примером является доказательство отсутствия алгоритма, позволяющего по произвольной контекстно-свободной грамматике узнать, является ли она неопределенной.
Интересной темой для исследования является связь между теорией контекстно-свободных языков и теорией автоматов. При этом каждая из этих теорий является инструментом и источником проблем для другой. На деле — так же как и в первых двух из приведенных выше примеров — часто трудно решить, относится ли данная проблема к теории автоматов или к теории языков. По существу содержание теории контекстно-свободных языков я рассматриваю как логическое продолжение теории автоматов. В частности, двухсеместровый курс лек- ций, прочитанный мною в Калифорнийском университете (Лос-Анжелес), был назван «Теория автоматов и контек- стно-свободных языков». Первая часть этого курса читалась по ранее написанному мной пособию [Gi 1], а вторая — по запискам, которые легли в основу настоящей книги. Часть курса, посвященная контекстно-свободным языкам, предназначалась для студентов, обладающих серьезной математической подготовкой и специализирующихся либо по математике (в особенности по математической логике), либо по математическому обеспечению машин (в особенности по программированию), либо по вычислительной технике. Замечания этих студентов оказались в высшей степени полезными для устранения ряда ошибок и уточнения некоторых доказательств.
Цель настоящей книги состоит в том, чтобы изложить ряд важных вопросов теории контекстно-свободных языков и приблизить читателя к переднему краю исследований в этой области. Важными признаются такие вопросы, которые либо A) используются в других частях теории, либо B) имеют отношение к естественным языкам или языкам программирования. Поэтому такие сами по себе интересные понятия, как последовательностные языки и металинейные языки, упомянуты лишь вскользь.
Рассматриваемый материал разделен на шесть глав (в их число не входит подготовительная глава, в которой приведены необходимые сведения из математики). В первой главе вводятся основные понятия, такие, как контекстно свободная грамматика, контекстно-свободный язык, дерево вывода, неопределенность, и приводятся некоторые элементарные сведения относительно этих понятий. Вторая глава посвящена регулярным множествам, конечным автоматам и автоматам с магазинной памятью. В этой главе дается характеристика регулярных множеств в терминах праволинейных (и леволинейных) грамматик и характеристика контекстно-свободных языков в терминах автоматов с магазинной памятью. В третьей главе изучаются операции, относительно которых класс всех контекстно-свободных языков является инвариантным. Здесь среди прочих результатов можно указать, например, следующие: A) пересечение произвольного контекстно-свободного языка и произвольного регулярного множества является контекстно-свободным языком; B) образ произвольного контекстно-свободного языка при отображении, осуществляемом конечным преобразователем, является также контекстно-свободным языком. Четвертая глава посвящена изучению алгоритмических проблем. Ее основные результаты состоят в доказательстве невозможности построения алгоритмов, дающих ответ на следующие вопросы: A) порождают ли две контекстно-свободные грамматики один и тот же контекстно-свободный язык; B) существует ли конечный преобразователь, осуществляющий нетривиальное отображение произвольного заданного контекстно-свободного языка в другой произвольный заданный контекстно-свободный язык; C) является ли произвольная наперед заданная контекстно-свободная грамматика неопределенной. В пятой главе рассматриваются ограниченные контекстно-свободные языки и полулинейные множества. В частности, приводится доказательство результата Парика об отображении контекстно-свободного языка на полулинейное множество; дается характеристика ограниченных контекстно-свободных языков, излагаются методы, позволяющие доказывать, что некоторые множества не являются контекстно-свободными языками. В шестой главе исследуется вопрос о существенной неопределенности. Выводится некоторое алгебраическое необходимое и достаточное условие существенной неопределенности ограниченного контекстно-свободного языка. Приводится также доказательство невозможности построения Предисловие автора 11 алгоритма, позволяющего по произвольному контекстно- свободному языку устанавливать, является ли он существенно неопределенным. В конце каждой главы приводится историческая справка. К книге приложена обширная библиография, включающая все использованные работы, в том числе и такие, на которые нет ссылок в тексте. Кроме того, в изложение включено большое число упражнений. Они не только обеспечивают более полное понимание материала, но и включают в себя некоторые менее важные вопросы теории. (Читателю следует иметь в виду, что среди упражений встречается немало громоздких и трудных.) Многие упражнения заимствованы из опубликованных работ или являются хорошо известными, но ранее не публиковались (везде, где это возможно, приводятся соответствующие ссылки). Остальные упражнения возникли в ходе бесед с Шейлой А. Грейбах, Томасом Н. Хиббардом, Джином Ф. Роузом, Эдвином X. Спэниером и Джозефом С. Уллиэном.
В разных местах в текст вкраплены некоторые нерешенные, т. е. открытые, вопросы и задачи, а также проблемы для исследования. Это сделано с целью наметить пути дальнейшей разработки теории. Я считаю, что мой труд окупится сторицей, если некоторые из указанных проблем и задач будут изучены и решены читателями.
Я выражаю глубокую благодарность Джину Ф. Роузу и Майклу Харрисону, скрупулезно прочитавшим рукопись. Слова признательности должны быть сказаны и в адрес моего коллеги Томаса Н. Хиббарда, с которым я неоднократно, с пользой для себя, обсуждал вторую главу. Я благодарен также В. Е. Синглетэри и X. Р. Эдмундсону за многочисленные предложения по улучшению изложения. Наконец, я хочу выразить глубокую благодарность Корпорации по разработке систем, которая финансировала работу по подготовке рукописи, а также постоянно создавала условия для моей научной деятельности в данной области.
Сеймур Гинзбург
(Для ознайомлення з повним текстом статті необхідно залогінитись)