Гладкий - Формальные грамматики и языки - 1973

613 Г 62 УДК 519-95 Формальные грамматики и языки. Гладкий А.В. Книга посвящена теории формальных грамматик и языков, являющейся важнейшей составной частью 'так называемой математической лингвистики. Эта теория вызвана к жизни потребностями лингвистики, но нашла сво)о почву в чистой математике и стала полноправной отраслью математической логики, тесно связанной с тео. рией алгоритмов и теорией автоматов. В книге рассматривается ряд важных проблем теории формальных грамматнк — таких, как взаимоотношения между различными классами грамматик п классами задаваемых ими языков, связь между грамматиками и автоматами, оценки сложностп вывода в грамматиках, алгоритмические проблемы для грамматик.

Книга представляет большой интерес для специалистов как в области математической лингвистики, так и в смежных областях, например в теории алгоритмов и автоматов. Страниц 368. Иллюстраций !7. Ллексей Всееолодоеыч Гладкой ФОРМАЛЬНЫЕ ГРАММАТИКИ И ЯЗЫКИ М„1979 г., Збз стр.

с ллл. Редактор В. В. Волченко Техн. редактор В. Б. Взмокал Корректор Н, Б, Ркмлккзео Слзоо з езоар ю)н11 )972 г.подписано к оечзтк з)н шуз г, пумегз 9)х)99)о. тко. Ль2. Фкз. оеч, л. )1,9. услоек. оеч. л. 19,92. уч -кзд. л, 29,29, Тквзж 7999 зкз'. 7.99799, Иекз кклгк ) р. 9)'к. Ззкзз № 279 Издзтельстзо чНзукзь Глззкзе редакция флзкко.мзтемзткческой лктерзтуры 117071, Москва, В-7), Леккксккй проспект, !3 Ордекз Трудового Красного Зкзмекк Лекеосрздскз» ткоогрзфнфз № 2 ямекк Еегекек Соколовой ° Совзоологрзфоромз» орн Госудзрстоелком «омктете Созетз Мнккстроз СССР по делам яздзтельстз колкгрзфкл к книжной торгоелв г.

Ленинград, Л.З2, 1чзмзйлозсккй кросоект, 29 Г 0223-1714 942 (02)-73 О ГЛАБЛ ЕН И Е Предисловие 5 Введение ' 9 Г л а в а 1. Основные понятия ............. 17 й 1.0. Некоторые предварительные пояснения,..., . 17 й 1:1. Цепочки и языки....,...,...., 19 $1:2. Грамматики......,........ 25 9 !.3. Примеры грамматик............. 33 $1.4. Машины Тьюринга.............. 39. Упражнения .................. 50 Глава 2. Сигнализирующие функции.....,.... 55 $2.1. Сигнализирующие функции грамматик...... 55 $2:2. Сигнализирующие функции машин Тьюринга..., 62 $2.3.

Ускорение и сжатие выводов. Связь между сигнализирующими грамматик и машин......... 84 $2,4. Существование сколь угодно сложных рекурсивных язь)ков ............,..... 71 Упражнения .................. 75 Глава 3. Грамматики составляющих.......... 79 9 3.1. Деревья выводов.............. 79 $3.2. Неукарачивающие грамматики и машины Тьюринга без растяжения............... 34 $ 3.3. Сложность вывода в неукорачивающих грамматиках и НС.грамматиках .............. 89 9 3:4. Оценка временнбй сложности некоторых НС-языков .

93 9 3.5. 'НС-грамматики с односторонним контекстом..., 195 Упран)ненив , Ц1. Г л а в а 4. Бесконтекстные грамматики и машины с магазинной памятью . 1!5 $4.1. Некоторые вспомогательные утверждения . . . . . 115 $4.2. Распознавание пустоты и конечности Б-языка, Проекции ',',',',' .' ..' .'....,..., .', 12! 6 4 3. Необходимые условия бесконтекстности . . . . . . 128 Ф 4.4. Неоднозначность . . . . .

. . . . . . . . . 134' 9 4.5. Машяны с магазинной памятью...,..... 137' Упражнения 152' 1 ° ОГЛАВЛЕНИЕ Глава 5. Некоторые специальные классы бесконтекстных языков , 157 $5сй Автоматные и обобщенные автоматные языки. Конечные автоматы . . . . . . . . . . . . , . . !57 $ 5.2. Операции над ОА-языками. Регулярные языки . .

. 162 6 5.3. Лиаейные, металинейные и итерационно.линейные языки . . . . . . . . . . . . . . . . , . 168 й 5.4. Грамматики с ограниченной активной емкостью выво. дов. ОАЕВ-языки . . . . . . . . . . . . . . !74 Упражнения ......,.....,,.... 179 Глава 6. Дополнительные сведения о бесковтекстных грамма- тиках. Другие способы задания бесконтекстных языков . . .

, . . . , . . . . . . . . . , . 185 й 6.!. Категориальиые грамматики . . . . . . . . . . 185 $6.2. Нормальная форма Б-грамматики . . . . . . . . 196 6 6.3. Доминационяые грамматики......., .. 200 й 6.4. Системы уравнений в языках. Формальные степенные ряды . 207 3 6.5. Каноническое представление Б-языка . . . . . . 213 Упражнения ............... 218 Глава 7. Сложность вывода в бесконтекстных грамматиках . 221 й 7.1. Глубина н разброс . 221 6 7.2, Активная емкость . . . .

. . . , , . . . . , 228 6 7Б. Степень гнездования и степень самовставления . . 242 Упражнения .................. 249 Глава 8. Неразрешимые алгоритмические проблемы.... 252 й 8.1. Предварительные замечания........., 252 8.2. Инвариаитные свойства произвольных грамматик .. 256 8.3. Ипвариантные свойства НС-грамматик..... 260 6 8.4.

Некоторые проблемы, связанные с Б-грамматиками . 268 Упражнения . 279 Приложение 1. Системы составляющих и деревья синтаксического подчинения . . . . . . . . . 282 6 П1.1. Системы составляющих.....,..... 282 й П1.2. Деревья подчинения . . . . . . . . . . , . 294 6 П1. 3. Связь между системами составляющих и деревьями подчинения...,..., .. 304 Упражнения ...............

310 Приложен не П. Замещаемасть ........... 314 й ПП.1. Свободные полугруппы.... ',...., . 3!5 й ПП. 2. Замещаемость и взаимозамещаемость. Конфигурации,..., .' .'......... 3!8 й ПП.З. Окрестности, классы и типы....,.... 324 Упражнения .......... 340 Библиографические замечании..., ° °....., . 343 Литература,............ 349 Предметный указатель , , . . . . . , . . . . 357 Указатель обозначений .

. . . . . . 367 ПРЕДИСЛОВИЕ Настоящая книга представляет собой руководство по теории формальных грамматик, предназначенное для тех, кто хочет познакомиться с ее современным состоянием достаточно основательно — в общеобразователь- ных целях или ради прикладных задач (например, свя- ванных с языками программирования). Это первая книга такого рода на русском языке; монография (О)пзЬпгд 1966) е), русский перевод которой вышел в !970 г., посвящена исключительно бескоитекстным языкам **); другая недавно переведенная книга (Огозз — Ьеп1[п 1967) значительно элементарнее и содержит лишь основные понятия теории формальных грамматике**). Книга адресована в первую очередь читателю-математику; во всяком случае, для ее чтения нужна'извест- ') Фамилия и год в квадратвых скобках — ссылка на помещенный в канде книги список литературы.

Если в списке указано не. сколько работ одного автора, имеющих один и тот же год издания, то добавляются буквы в круглых скобках, например [СЬошзку 1959[б)1. "*) Кроме тато, в настоящей книге изложены некоторые разделы теории бесконтекстных языков, которых нет в [СипэЬпгк 19661: оценки сложности вывода, категориальные и доминациоиные грамматики, металинейные и итерационно-лннейные языки; подробнее трактуются алгоритмические проблемы.

С другой стороны, мы не рассматриваем преобразователей и ограниченных бесконтекстных языков, изучению которых уделено много внимания в кинге С. Гинзбурга. Еще одно отличие нашей книги от названной — мевьшая формализозанность изложения. "") Кроме названных двух, в мировой литературе имеется (на. сколько известно автору] еще только одна книга по формальным языкам [Норсгон — 1)!)шап 19691, также довольно сильно отлича|о1цаяся по содержанию от нашей.

прадисловие ная привычка к математическому мышлению и изучению математической литературы, Что касается фактических знаний, то формально их почти не требуется: достаточно владеть основными понятиями теории множеств. Тем не менее весьма желательно предварительное знакомство хотя бы с главными идеями и концепциями теории алгоритмов, в частности с машинами Тьюринга, поскольку «алгорнтмический дух» пронизынает всю теорию грамматик; не приобщившись к нему, невозможно составить представление о месте формальных грамматик в математике. При этом речь идет именно о направляющих идеях и общем духе: все относящиеся к алгоритмам технические определения — в терминах машин Тьюринга — в книге приводятся, и все необходимые факты доказываются *).

Лингвистические интерпретации упоминаются в основном тексте книги лишь изредка и вскользь (больше' внимания им уделено в приложениях 1 и П, но рассматриваемый там материал не относится, строга говоря, к грамматикам). Однако знакомство с лингвистическим' аспектом теории грамматик представляется автору полезным для ее изучения даже в чисто математическом плане; для ознакомления с этим аспектом можно рекомендовать книгу ~Гладкий — Мельчук 1969].

«Программистских» приложений мы не касаемся. В конце каждой главы помещены упражнения. Не- ' которые из них носят чисто тренировочный характер, но большинство предназначено служить дополнением к основному тексту; в упражнения вынесены многие факты, наличие которых в тексте не обязательно для логической последовательности изложения, а в отдельных случаях и такие утверждения, которые в дальнейшем ис- ") В частности, полностью замкнутым в себе сделано изложение нервврешимых алгоритмических проблем (гл. 8). Иэ теории влгоритмов в этом изложении используется только теорема Рейсе, докаввтельство которой приводится твм же.

првдисловив пользуются, если их доказательства просты и основаны на уже «отработанной» технике. Диапазон трудности упражнений весьма широк; к некоторым из наиболее трудных и наиболее важных даны краткие указания. Список литературы не претендует ни на какое подобие полноты; в него включены только те работы, которые упоминаются в книге, главным образом в библиографических замечаниях, также не претендующих на полный охват относящихся к делу источников.