Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
§ 6.5. Каноническое представление Б-языка..................213
Упражнения ................................................218
Глава 7. Сложность вывода в бесконтекстных грамматиках . 221
§ 7.1. Глубина и разброс...................................221
§ 7.2. Активная емкость....................................228
§ 7.'3. Степень гнездования и степень самовставления . . 242 Упражнения .............................................249
Глава 8. Неразрешимые алгоритмические проблемы .... 252
§ 8.1. Предварительные замечания........................... 252
§ 8.2. Инвариантные свойства произвольных грамматик . . 256
§ 8.3. Инвариантные свойства НС-грамматик..................260
§ 8.4. Некоторые проблемы, связанные с Б-грамматиками . 268 Упражнения .............................................279
Приложение I. Системы составляющих и деревья синтаксического подчинения.............................................282
§ П1.1. Системы составляющих...............................282
§ П1.2. Деревья подчинения............................ 294
§ П1. 3. Связь между системами составляющих и деревьями
подчинения..........................................304
Упражнения ........................................ 310
Приложение II. Замещаемость....................................314
§ ПП. 1. Свободные полугруппы .............................315
§ ПП. 2. Замещаемость и взаимозамещаемость. Конфигурации ......................... ..........................318
§ ПП. 3. Окрестности, классы и типы........................324
Упражнения ................................................340
Библиографические замечания....................................343
Литература ’ ...........................................349
Предметный указатель . < . . ..................................357
Указатель обозначений .........................................367
ПРЕДИСЛОВИЕ
Настоящая книга представляет собой руководство по теории формальных грамматик, предназначенное для тех, кто хочет познакомиться с ее современным состоянием достаточно основательно — в общеобразовательных целях или ради прикладных задач (например, связанных с языками программирования). Это первая книга такого рода на русском языке; монография [Gins-burg 1966]*), русский перевод которой вышел в 1970 г., посвящена исключительно бесконтекстным языкам**); другая недавно переведенная книга [Gross — Lentin 1967] значительно элементарнее и содержит лишь основные понятия теории формальных грамматик***).
Книга адресована в первую очередь читателю-мате-матику; во всяком случае, для ее чтения нужна- извест-
*) Фамилия и год в квадратных скобках — ссылка на помещенный в конце книги список литературы. Если в списке указано несколько работ одного автора, имеющих один и тот же год издания, то добавляются буквы в круглых скобках, например [Chomsky 1959(6)].
**) Кроме того, в настоящей книге изложены некоторые разделы теории бесконтекстных языков, которых нет в [Ginsburg 1966]: оценки сложности вывода, категориальные и доминационные грамматики, металинейные и итерационно-линейные языки; подробнее трактуются алгоритмические проблемы. С другой стороны, мы не рассматриваем преобразователей и ограниченных бесконтекстных языков, изучению которых уделено много внимания в книге С. Гинзбурга. Еще одно отличие нашей книги от названной — меньшая фор~ Мализованность изложения.
***) Кроме названных двух, в мировой литературе имеется (насколько известно автору) еще только одна книга по формальным языкам [Hopcroft — Ullman 1969], также довольно сильно отличающаяся по содержанию от нашей.
6
ПРЕДИСЛОВИЕ
ная привычка к математическому мышлению и изучению математической литературы. Что касается фактических знаний, то формально их почти не требуется: достаточно владеть основными понятиями теории множеств. Тем не менее весьма желательно предварительное знакомство хотя бы с главными идеями и концепциями теории алгоритмов, в частности с машинами Тьюринга, поскольку «алгоритмический дух» пронизывает всю теорию грамматик; не приобщившись к нему, невозможно составить представление о месте формальных грамматик в математике. При этом речь идет именно о направляющих идеях и общем духе: все относящиеся к алгоритмам технические определения — в терминах машин Тьюринга — в книге приводятся, и все необходимые факты доказываются *).
Лингвистические интерпретации упоминаются в основном тексте книги лишь изредка и вскользь (больше внимания им уделено в приложениях I и II, но рассматриваемый там материал не относится, строго говоря, к грамматикам). Однако знакомство с лингвистическим' аспектом теории грамматик представляется автору полезным для ее изучения даже в чисто математическом плане; для ознакомления с этим аспектом можно рекомендовать книгу [Гладкий — Мельчук 1969]. «Программистских» приложений мы не касаемся.
В конце каждой главы помещены упражнения. Некоторые из них носят чисто тренировочный характер, но большинство предназначено служить дополнением к основному тексту; в упражнения вынесены многие факты, наличие которых в тексте не обязательно для логической последовательности изложения, а в отдельных случаях и такие утверждения, которые в дальнейшем ис-
